# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
46819 | 2018-04-23T16:40:24 Z | ffresh | 스트랩 (JOI14_straps) | C++17 | 8 ms | 1984 KB |
#include <bits/stdc++.h> using namespace std; #define ll long long const int N = 2005; int dp[N]; int pre[N]; int main(){ //freopen("input.txt","r",stdin); int n; scanf("%d",&n); int a,b; vector<pair<int,int> > bag; int cur = 1,cost = 0; int pos= 1; for(int i=1;i<=n+1;++i)dp[i]= -2e9-150; dp[1]= 0; for(int i=0;i<n;++i){ scanf("%d%d",&a,&b); if(b<0){ if(a<=1)continue; bag.push_back(make_pair(a,b)); } else{ if(a==0){ pre[pos++]= b; } else{ cur += a-1; cost +=b; } } } sort(pre+1,pre+pos,greater<int>()); for(int i=1;i<=n;++i) pre[i]= pre[i-1] + pre[i]; dp[cur]= cost; for(int i=0;i<bag.size();++i){ a = bag[i].first, b= bag[i].second; for(int j=n;j>=cur;--j){ int nb = min(n ,j +a-1); dp[nb]= max(dp[nb],dp[j]+b); } } int ret= 0; for(int i=cur;i<=n;++i){ int sz= i; ret = max(ret, dp[i] + pre[sz]); } cout<<ret<<endl; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 248 KB | Output is correct |
2 | Correct | 2 ms | 488 KB | Output is correct |
3 | Correct | 2 ms | 488 KB | Output is correct |
4 | Correct | 2 ms | 488 KB | Output is correct |
5 | Correct | 2 ms | 488 KB | Output is correct |
6 | Correct | 2 ms | 488 KB | Output is correct |
7 | Correct | 2 ms | 508 KB | Output is correct |
8 | Correct | 2 ms | 508 KB | Output is correct |
9 | Correct | 2 ms | 604 KB | Output is correct |
10 | Correct | 2 ms | 756 KB | Output is correct |
11 | Correct | 2 ms | 756 KB | Output is correct |
12 | Correct | 2 ms | 756 KB | Output is correct |
13 | Correct | 2 ms | 756 KB | Output is correct |
14 | Correct | 2 ms | 840 KB | Output is correct |
15 | Correct | 2 ms | 840 KB | Output is correct |
16 | Correct | 2 ms | 840 KB | Output is correct |
17 | Correct | 2 ms | 840 KB | Output is correct |
18 | Correct | 2 ms | 844 KB | Output is correct |
19 | Correct | 2 ms | 844 KB | Output is correct |
20 | Correct | 2 ms | 872 KB | Output is correct |
21 | Correct | 2 ms | 872 KB | Output is correct |
22 | Correct | 2 ms | 872 KB | Output is correct |
23 | Correct | 2 ms | 872 KB | Output is correct |
24 | Incorrect | 2 ms | 872 KB | Output isn't correct |
25 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 872 KB | Output is correct |
2 | Correct | 2 ms | 872 KB | Output is correct |
3 | Correct | 2 ms | 872 KB | Output is correct |
4 | Correct | 2 ms | 872 KB | Output is correct |
5 | Correct | 2 ms | 872 KB | Output is correct |
6 | Correct | 2 ms | 872 KB | Output is correct |
7 | Correct | 2 ms | 872 KB | Output is correct |
8 | Correct | 2 ms | 972 KB | Output is correct |
9 | Correct | 3 ms | 972 KB | Output is correct |
10 | Correct | 3 ms | 972 KB | Output is correct |
11 | Correct | 2 ms | 972 KB | Output is correct |
12 | Correct | 3 ms | 1068 KB | Output is correct |
13 | Correct | 2 ms | 1068 KB | Output is correct |
14 | Correct | 2 ms | 1068 KB | Output is correct |
15 | Correct | 3 ms | 1068 KB | Output is correct |
16 | Correct | 2 ms | 1068 KB | Output is correct |
17 | Correct | 3 ms | 1068 KB | Output is correct |
18 | Correct | 2 ms | 1068 KB | Output is correct |
19 | Correct | 2 ms | 1100 KB | Output is correct |
20 | Correct | 3 ms | 1116 KB | Output is correct |
21 | Incorrect | 2 ms | 1136 KB | Output isn't correct |
22 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 1136 KB | Output is correct |
2 | Correct | 2 ms | 1160 KB | Output is correct |
3 | Correct | 2 ms | 1164 KB | Output is correct |
4 | Correct | 2 ms | 1164 KB | Output is correct |
5 | Correct | 2 ms | 1172 KB | Output is correct |
6 | Correct | 2 ms | 1176 KB | Output is correct |
7 | Correct | 2 ms | 1180 KB | Output is correct |
8 | Correct | 2 ms | 1180 KB | Output is correct |
9 | Correct | 2 ms | 1188 KB | Output is correct |
10 | Correct | 3 ms | 1188 KB | Output is correct |
11 | Correct | 2 ms | 1228 KB | Output is correct |
12 | Correct | 2 ms | 1240 KB | Output is correct |
13 | Correct | 2 ms | 1252 KB | Output is correct |
14 | Correct | 2 ms | 1264 KB | Output is correct |
15 | Correct | 2 ms | 1276 KB | Output is correct |
16 | Correct | 2 ms | 1276 KB | Output is correct |
17 | Correct | 3 ms | 1428 KB | Output is correct |
18 | Correct | 3 ms | 1428 KB | Output is correct |
19 | Correct | 3 ms | 1428 KB | Output is correct |
20 | Correct | 3 ms | 1428 KB | Output is correct |
21 | Correct | 3 ms | 1428 KB | Output is correct |
22 | Correct | 3 ms | 1432 KB | Output is correct |
23 | Correct | 3 ms | 1432 KB | Output is correct |
24 | Correct | 3 ms | 1444 KB | Output is correct |
25 | Correct | 3 ms | 1464 KB | Output is correct |
26 | Correct | 3 ms | 1484 KB | Output is correct |
27 | Correct | 3 ms | 1608 KB | Output is correct |
28 | Correct | 2 ms | 1736 KB | Output is correct |
29 | Correct | 3 ms | 1736 KB | Output is correct |
30 | Correct | 3 ms | 1736 KB | Output is correct |
31 | Correct | 2 ms | 1736 KB | Output is correct |
32 | Correct | 3 ms | 1736 KB | Output is correct |
33 | Correct | 8 ms | 1752 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1808 KB | Output is correct |
2 | Correct | 2 ms | 1808 KB | Output is correct |
3 | Correct | 3 ms | 1828 KB | Output is correct |
4 | Correct | 3 ms | 1848 KB | Output is correct |
5 | Correct | 2 ms | 1900 KB | Output is correct |
6 | Correct | 2 ms | 1920 KB | Output is correct |
7 | Correct | 2 ms | 1944 KB | Output is correct |
8 | Correct | 2 ms | 1964 KB | Output is correct |
9 | Incorrect | 2 ms | 1984 KB | Output isn't correct |
10 | Halted | 0 ms | 0 KB | - |