Submission #1913713
Source Code Expand
import java.io.*; import java.util.*; class Main { static final long I=1L<<53; static void mEqN(int n,int k,long[]a){ long[]ans=new long[k+1]; Arrays.fill(ans,-I); ans[0]=0; for(int i=0;i<n;++i){ for(int j=Math.min(i+1,k);j>=1;--j){ ans[j]=Math.max(ans[j],ans[j-1]+j*a[i]); } } out.println(ans[k]); } 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]; int s=0,t=0; for(int i=1;i<k;++i){ 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; } } } class MaxSegmentTree { static final int SIZE = 1 << 18; static final long INFINITY = (1L << 62) - 1; long[] seg; MaxSegmentTree() { this.seg = new long[2 * SIZE]; } void update(int x, long value) { x += SIZE - 1; this.seg[x] = value; while (x > 0) { x = (x - 1) / 2; this.seg[x] = Math.max(this.seg[2 * x + 1], this.seg[2 * x + 2]); } } long query(int l, int r) { l += SIZE - 1; r += SIZE - 1; long y = -INFINITY; while (l < r) { if ((l & 1) == 0) { y = Math.max(y, this.seg[l]); } if ((r & 1) == 0) { y = Math.max(y, this.seg[r - 1]); } l /= 2; r = (r - 1) / 2; } return y; } }
Submission Info
Submission Time | |
---|---|
Task | A - Struck Out |
User | kirika_comp |
Language | Java8 (OpenJDK 1.8.0) |
Score | 700 |
Code Size | 3607 Byte |
Status | AC |
Exec Time | 741 ms |
Memory | 48372 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 | 69 ms | 18132 KB |
sample_2.txt | AC | 69 ms | 18644 KB |
sample_3.txt | AC | 69 ms | 17364 KB |
subtask_1_1.txt | AC | 70 ms | 21332 KB |
subtask_1_2.txt | AC | 169 ms | 25300 KB |
subtask_1_3.txt | AC | 677 ms | 38464 KB |
subtask_1_4.txt | AC | 113 ms | 22356 KB |
subtask_1_5.txt | AC | 197 ms | 41560 KB |
subtask_1_6.txt | AC | 76 ms | 21204 KB |
subtask_1_7.txt | AC | 357 ms | 40744 KB |
subtask_1_8.txt | AC | 717 ms | 39920 KB |
subtask_1_9.txt | AC | 96 ms | 19028 KB |
subtask_2_1.txt | AC | 74 ms | 19284 KB |
subtask_2_2.txt | AC | 84 ms | 19796 KB |
subtask_2_3.txt | AC | 75 ms | 21460 KB |
subtask_2_4.txt | AC | 74 ms | 18388 KB |
subtask_2_5.txt | AC | 70 ms | 21204 KB |
subtask_2_6.txt | AC | 69 ms | 18772 KB |
subtask_2_7.txt | AC | 73 ms | 18132 KB |
subtask_2_8.txt | AC | 73 ms | 21332 KB |
subtask_2_9.txt | AC | 75 ms | 21332 KB |
subtask_3_1.txt | AC | 275 ms | 48372 KB |
subtask_3_2.txt | AC | 264 ms | 40148 KB |
subtask_3_3.txt | AC | 272 ms | 44532 KB |
subtask_3_4.txt | AC | 247 ms | 34136 KB |
subtask_3_5.txt | AC | 113 ms | 20436 KB |
subtask_3_6.txt | AC | 247 ms | 42072 KB |
subtask_3_7.txt | AC | 256 ms | 43352 KB |
subtask_3_8.txt | AC | 122 ms | 23892 KB |
subtask_3_9.txt | AC | 282 ms | 42588 KB |
subtask_4_1.txt | AC | 697 ms | 41588 KB |
subtask_4_10.txt | AC | 393 ms | 41424 KB |
subtask_4_11.txt | AC | 686 ms | 45912 KB |
subtask_4_12.txt | AC | 686 ms | 40408 KB |
subtask_4_13.txt | AC | 706 ms | 41920 KB |
subtask_4_2.txt | AC | 677 ms | 42024 KB |
subtask_4_3.txt | AC | 741 ms | 41596 KB |
subtask_4_4.txt | AC | 686 ms | 39992 KB |
subtask_4_5.txt | AC | 622 ms | 39644 KB |
subtask_4_6.txt | AC | 260 ms | 43732 KB |
subtask_4_7.txt | AC | 487 ms | 44444 KB |
subtask_4_8.txt | AC | 678 ms | 40796 KB |
subtask_4_9.txt | AC | 418 ms | 41304 KB |