Submission #1913691
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[2]; 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){ int u=(i-1)%2; int nxt=1-u; for(int j=i;j<n;++j){ long val=seg[u].query(Math.max(i-1,j-m),j)+(i+1)*a[j]; seg[nxt].update(j,val); } } out.println(seg[(k-1)%2].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(); } if(n==m){ mEqN(n,k,a); }else{ 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 | 600 |
Code Size | 3430 Byte |
Status | TLE |
Exec Time | 2109 ms |
Memory | 45012 KB |
Judge Result
Set Name | Sample | subtask1 | subtask2 | subtask3 | All | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 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 | 169 ms | 31956 KB |
sample_2.txt | AC | 70 ms | 18388 KB |
sample_3.txt | AC | 148 ms | 31828 KB |
subtask_1_1.txt | AC | 74 ms | 21332 KB |
subtask_1_2.txt | AC | 120 ms | 23252 KB |
subtask_1_3.txt | AC | 263 ms | 34492 KB |
subtask_1_4.txt | AC | 102 ms | 21844 KB |
subtask_1_5.txt | AC | 172 ms | 33856 KB |
subtask_1_6.txt | AC | 74 ms | 19412 KB |
subtask_1_7.txt | AC | 226 ms | 34440 KB |
subtask_1_8.txt | AC | 242 ms | 35724 KB |
subtask_1_9.txt | AC | 84 ms | 21588 KB |
subtask_2_1.txt | AC | 154 ms | 34260 KB |
subtask_2_2.txt | AC | 161 ms | 36180 KB |
subtask_2_3.txt | AC | 161 ms | 31956 KB |
subtask_2_4.txt | AC | 75 ms | 23252 KB |
subtask_2_5.txt | AC | 149 ms | 31188 KB |
subtask_2_6.txt | AC | 70 ms | 19796 KB |
subtask_2_7.txt | AC | 160 ms | 36948 KB |
subtask_2_8.txt | AC | 166 ms | 34260 KB |
subtask_2_9.txt | AC | 152 ms | 34388 KB |
subtask_3_1.txt | AC | 756 ms | 41312 KB |
subtask_3_2.txt | AC | 678 ms | 45012 KB |
subtask_3_3.txt | AC | 677 ms | 43236 KB |
subtask_3_4.txt | AC | 651 ms | 44184 KB |
subtask_3_5.txt | AC | 213 ms | 32852 KB |
subtask_3_6.txt | AC | 402 ms | 43632 KB |
subtask_3_7.txt | AC | 732 ms | 44328 KB |
subtask_3_8.txt | AC | 242 ms | 36436 KB |
subtask_3_9.txt | AC | 525 ms | 40880 KB |
subtask_4_1.txt | TLE | 2109 ms | 41756 KB |
subtask_4_10.txt | TLE | 2109 ms | 42588 KB |
subtask_4_11.txt | TLE | 2109 ms | 43292 KB |
subtask_4_12.txt | TLE | 2109 ms | 42264 KB |
subtask_4_13.txt | TLE | 2109 ms | 41120 KB |
subtask_4_2.txt | TLE | 2109 ms | 42528 KB |
subtask_4_3.txt | TLE | 2109 ms | 41316 KB |
subtask_4_4.txt | TLE | 2109 ms | 43292 KB |
subtask_4_5.txt | TLE | 2109 ms | 43292 KB |
subtask_4_6.txt | AC | 614 ms | 42908 KB |
subtask_4_7.txt | AC | 1891 ms | 40732 KB |
subtask_4_8.txt | TLE | 2109 ms | 44448 KB |
subtask_4_9.txt | AC | 1905 ms | 42728 KB |