# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
55137 | 2018-07-06T06:05:44 Z | khsoo01(#2065) | None (JOI14_ho_t2) | C++11 | 44 ms | 20348 KB |
#include<bits/stdc++.h> using namespace std; const int N = 10005, M = 505, inf = 1e9; int n, m, a[N], s[M], v[M], dt[M][N]; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); dt[0][i] = inf; } for(int i=1;i<=m;i++) { scanf("%d%d",&s[i],&v[i]); for(int j=1;j<=n;j++) { dt[i][j] = dt[i-1][j]; } for(int j=0;j<=n;j++) { int J = min(n,j+s[i]); dt[i][J] = min(dt[i][J], dt[i-1][j] + v[i]); } } for(int i=n;--i;) { dt[m][i] = min(dt[m][i], dt[m][i+1]); } sort(a+1, a+1+n); reverse(a+1, a+1+n); int ans = 0; for(int i=1;i<=n;i++) { a[i] += a[i-1]; ans = max(ans, a[i] - dt[m][i]); } printf("%d\n",ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 248 KB | Output is correct |
2 | Correct | 2 ms | 360 KB | Output is correct |
3 | Correct | 5 ms | 944 KB | Output is correct |
4 | Correct | 4 ms | 1004 KB | Output is correct |
5 | Correct | 5 ms | 1004 KB | Output is correct |
6 | Correct | 2 ms | 1004 KB | Output is correct |
7 | Correct | 2 ms | 1004 KB | Output is correct |
8 | Correct | 3 ms | 1004 KB | Output is correct |
9 | Correct | 4 ms | 1080 KB | Output is correct |
10 | Correct | 6 ms | 1128 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 26 ms | 20216 KB | Output is correct |
2 | Correct | 35 ms | 20216 KB | Output is correct |
3 | Correct | 34 ms | 20216 KB | Output is correct |
4 | Correct | 41 ms | 20216 KB | Output is correct |
5 | Correct | 32 ms | 20348 KB | Output is correct |
6 | Correct | 7 ms | 20348 KB | Output is correct |
7 | Correct | 31 ms | 20348 KB | Output is correct |
8 | Correct | 35 ms | 20348 KB | Output is correct |
9 | Correct | 7 ms | 20348 KB | Output is correct |
10 | Correct | 44 ms | 20348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 248 KB | Output is correct |
2 | Correct | 2 ms | 360 KB | Output is correct |
3 | Correct | 5 ms | 944 KB | Output is correct |
4 | Correct | 4 ms | 1004 KB | Output is correct |
5 | Correct | 5 ms | 1004 KB | Output is correct |
6 | Correct | 2 ms | 1004 KB | Output is correct |
7 | Correct | 2 ms | 1004 KB | Output is correct |
8 | Correct | 3 ms | 1004 KB | Output is correct |
9 | Correct | 4 ms | 1080 KB | Output is correct |
10 | Correct | 6 ms | 1128 KB | Output is correct |
11 | Correct | 26 ms | 20216 KB | Output is correct |
12 | Correct | 35 ms | 20216 KB | Output is correct |
13 | Correct | 34 ms | 20216 KB | Output is correct |
14 | Correct | 41 ms | 20216 KB | Output is correct |
15 | Correct | 32 ms | 20348 KB | Output is correct |
16 | Correct | 7 ms | 20348 KB | Output is correct |
17 | Correct | 31 ms | 20348 KB | Output is correct |
18 | Correct | 35 ms | 20348 KB | Output is correct |
19 | Correct | 7 ms | 20348 KB | Output is correct |
20 | Correct | 44 ms | 20348 KB | Output is correct |
21 | Correct | 38 ms | 20348 KB | Output is correct |
22 | Correct | 34 ms | 20348 KB | Output is correct |
23 | Correct | 31 ms | 20348 KB | Output is correct |
24 | Correct | 36 ms | 20348 KB | Output is correct |
25 | Correct | 32 ms | 20348 KB | Output is correct |
26 | Correct | 31 ms | 20348 KB | Output is correct |
27 | Correct | 11 ms | 20348 KB | Output is correct |
28 | Correct | 35 ms | 20348 KB | Output is correct |
29 | Correct | 35 ms | 20348 KB | Output is correct |
30 | Correct | 30 ms | 20348 KB | Output is correct |