Submission #1913685
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){ MaxSegmentTree[]seg=new MaxSegmentTree[k]; Arrays.setAll(seg,x->new MaxSegmentTree()); for(int i=0;i<n;++i){ seg[0].update(i,a[i]); } for(int i=1;i<k;++i){ for(int j=i;j<n;++j){ long val=seg[i-1].query(Math.max(i-1,j-m),j)+(i+1)*a[j]; seg[i].update(j,val); } } out.println(seg[k-1].query(k-1,n)); } 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 | 500 |
Code Size | 3296 Byte |
Status | TLE |
Exec Time | 2112 ms |
Memory | 894716 KB |
Judge Result
Set Name | Sample | subtask1 | subtask2 | subtask3 | All | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 100 | 200 / 200 | 300 / 300 | 0 / 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 | 150 ms | 34388 KB |
sample_2.txt | AC | 147 ms | 31700 KB |
sample_3.txt | AC | 163 ms | 51284 KB |
subtask_1_1.txt | AC | 219 ms | 169040 KB |
subtask_1_2.txt | MLE | 877 ms | 884816 KB |
subtask_1_3.txt | MLE | 881 ms | 839500 KB |
subtask_1_4.txt | AC | 278 ms | 172240 KB |
subtask_1_5.txt | AC | 355 ms | 55004 KB |
subtask_1_6.txt | MLE | 612 ms | 874320 KB |
subtask_1_7.txt | MLE | 1946 ms | 554200 KB |
subtask_1_8.txt | MLE | 774 ms | 847388 KB |
subtask_1_9.txt | MLE | 657 ms | 874576 KB |
subtask_2_1.txt | AC | 222 ms | 159312 KB |
subtask_2_2.txt | AC | 169 ms | 76372 KB |
subtask_2_3.txt | AC | 199 ms | 119636 KB |
subtask_2_4.txt | AC | 225 ms | 162256 KB |
subtask_2_5.txt | AC | 222 ms | 162124 KB |
subtask_2_6.txt | AC | 217 ms | 161996 KB |
subtask_2_7.txt | AC | 222 ms | 159824 KB |
subtask_2_8.txt | AC | 216 ms | 160848 KB |
subtask_2_9.txt | AC | 226 ms | 153932 KB |
subtask_3_1.txt | AC | 790 ms | 162100 KB |
subtask_3_2.txt | AC | 738 ms | 166032 KB |
subtask_3_3.txt | AC | 745 ms | 164396 KB |
subtask_3_4.txt | AC | 683 ms | 167032 KB |
subtask_3_5.txt | AC | 281 ms | 160720 KB |
subtask_3_6.txt | AC | 431 ms | 98440 KB |
subtask_3_7.txt | AC | 787 ms | 165396 KB |
subtask_3_8.txt | AC | 313 ms | 160656 KB |
subtask_3_9.txt | AC | 608 ms | 164936 KB |
subtask_4_1.txt | MLE | 776 ms | 851204 KB |
subtask_4_10.txt | MLE | 760 ms | 848536 KB |
subtask_4_11.txt | MLE | 791 ms | 894716 KB |
subtask_4_12.txt | MLE | 751 ms | 845968 KB |
subtask_4_13.txt | MLE | 764 ms | 849064 KB |
subtask_4_2.txt | MLE | 751 ms | 844160 KB |
subtask_4_3.txt | MLE | 739 ms | 849048 KB |
subtask_4_4.txt | MLE | 749 ms | 846356 KB |
subtask_4_5.txt | MLE | 749 ms | 849564 KB |
subtask_4_6.txt | AC | 662 ms | 132376 KB |
subtask_4_7.txt | TLE | 2112 ms | 756104 KB |
subtask_4_8.txt | MLE | 751 ms | 846892 KB |
subtask_4_9.txt | TLE | 2111 ms | 598680 KB |