Submission #1913715
Source Code Expand
import java.io.*; import java.util.*; class Main { static void solve(int n,int m,int k,long[]a){ long[][]dp=new long[2][n]; for(int i=0;i<n;++i){ dp[0][i]=a[i]; } int[]deq=new int[n]; for(int i=1;i<k;++i){ int s=0,t=0; int u=(i-1)%2; int nxt=1-u; for(int j=i-1;j<n;++j){ if(j>=i){ assert s < t; long val=dp[u][deq[s]]+(i+1)*a[j]; dp[nxt][j]=val; if(deq[s]==j-m)s++; } while(s<t&&dp[u][deq[t-1]]<=dp[u][j])t--; deq[t++]=j; } } long ans=0; for(int i=k-1;i<n;++i)ans=Math.max(ans,dp[(k-1)%2][i]); out.println(ans); } public static void main(String[] args) { MyScanner sc = new MyScanner(); out = new PrintWriter(new BufferedOutputStream(System.out)); int n=sc.nextInt(); int m=sc.nextInt(); int k=sc.nextInt(); long[]a=new long[n]; for(int i=0;i<n;++i){ a[i]=sc.nextLong(); } solve(n,m,k,a); out.close(); } // http://codeforces.com/blog/entry/7018 //-----------PrintWriter for faster output--------------------------------- public static PrintWriter out; //-----------MyScanner class for faster input---------- public static class MyScanner { BufferedReader br; StringTokenizer st; public MyScanner() { br = new BufferedReader(new InputStreamReader(System.in)); } String next() { while (st == null || !st.hasMoreElements()) { try { st = new StringTokenizer(br.readLine()); } catch (IOException e) { e.printStackTrace(); } } return st.nextToken(); } int nextInt() { return Integer.parseInt(next()); } long nextLong() { return Long.parseLong(next()); } double nextDouble() { return Double.parseDouble(next()); } String nextLine(){ String str = ""; try { str = br.readLine(); } catch (IOException e) { e.printStackTrace(); } return str; } } }
Submission Info
Submission Time | |
---|---|
Task | A - Struck Out |
User | kirika_comp |
Language | Java8 (OpenJDK 1.8.0) |
Score | 700 |
Code Size | 2518 Byte |
Status | AC |
Exec Time | 732 ms |
Memory | 44532 KB |
Judge Result
Set Name | Sample | subtask1 | subtask2 | subtask3 | All | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | 200 / 200 | 300 / 300 | 100 / 100 | ||||||||||
Status |
|
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_1.txt, sample_2.txt, sample_3.txt |
subtask1 | sample_2.txt, subtask_1_1.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt |
subtask2 | sample_1.txt, sample_2.txt, sample_3.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt |
subtask3 | sample_1.txt, sample_2.txt, sample_3.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt, subtask_3_1.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt, subtask_3_9.txt |
All | sample_1.txt, sample_2.txt, sample_3.txt, sample_1.txt, sample_2.txt, sample_3.txt, subtask_1_1.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt, subtask_3_1.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt, subtask_3_9.txt, subtask_4_1.txt, subtask_4_10.txt, subtask_4_11.txt, subtask_4_12.txt, subtask_4_13.txt, subtask_4_2.txt, subtask_4_3.txt, subtask_4_4.txt, subtask_4_5.txt, subtask_4_6.txt, subtask_4_7.txt, subtask_4_8.txt, subtask_4_9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_1.txt | AC | 73 ms | 22480 KB |
sample_2.txt | AC | 70 ms | 21204 KB |
sample_3.txt | AC | 71 ms | 15828 KB |
subtask_1_1.txt | AC | 73 ms | 18004 KB |
subtask_1_2.txt | AC | 193 ms | 25936 KB |
subtask_1_3.txt | AC | 694 ms | 44324 KB |
subtask_1_4.txt | AC | 112 ms | 21332 KB |
subtask_1_5.txt | AC | 203 ms | 41996 KB |
subtask_1_6.txt | AC | 76 ms | 21332 KB |
subtask_1_7.txt | AC | 373 ms | 38028 KB |
subtask_1_8.txt | AC | 731 ms | 41740 KB |
subtask_1_9.txt | AC | 97 ms | 20308 KB |
subtask_2_1.txt | AC | 84 ms | 21332 KB |
subtask_2_2.txt | AC | 84 ms | 20820 KB |
subtask_2_3.txt | AC | 76 ms | 21460 KB |
subtask_2_4.txt | AC | 74 ms | 18644 KB |
subtask_2_5.txt | AC | 72 ms | 17108 KB |
subtask_2_6.txt | AC | 73 ms | 21072 KB |
subtask_2_7.txt | AC | 78 ms | 21456 KB |
subtask_2_8.txt | AC | 75 ms | 18260 KB |
subtask_2_9.txt | AC | 75 ms | 21460 KB |
subtask_3_1.txt | AC | 270 ms | 42048 KB |
subtask_3_2.txt | AC | 249 ms | 41376 KB |
subtask_3_3.txt | AC | 258 ms | 38720 KB |
subtask_3_4.txt | AC | 253 ms | 33984 KB |
subtask_3_5.txt | AC | 99 ms | 20564 KB |
subtask_3_6.txt | AC | 246 ms | 44532 KB |
subtask_3_7.txt | AC | 269 ms | 42068 KB |
subtask_3_8.txt | AC | 135 ms | 23380 KB |
subtask_3_9.txt | AC | 266 ms | 42084 KB |
subtask_4_1.txt | AC | 687 ms | 40024 KB |
subtask_4_10.txt | AC | 377 ms | 42876 KB |
subtask_4_11.txt | AC | 691 ms | 39872 KB |
subtask_4_12.txt | AC | 713 ms | 42332 KB |
subtask_4_13.txt | AC | 723 ms | 42540 KB |
subtask_4_2.txt | AC | 693 ms | 42092 KB |
subtask_4_3.txt | AC | 732 ms | 41816 KB |
subtask_4_4.txt | AC | 680 ms | 38208 KB |
subtask_4_5.txt | AC | 631 ms | 42152 KB |
subtask_4_6.txt | AC | 245 ms | 41100 KB |
subtask_4_7.txt | AC | 466 ms | 41192 KB |
subtask_4_8.txt | AC | 692 ms | 43992 KB |
subtask_4_9.txt | AC | 424 ms | 40616 KB |