oj.uz

Submission #25189

# Submission time Handle Problem Language Result Execution time Memory
25189 2017-06-20T15:52:05 Z junodeveloper 스트랩 (JOI14_straps) C++14
100 / 100
 13 ms 33368 KB 
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define INF (ll)2e9
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pl;
ll n,i,d[2002][2002];
pl p[2002];
vector<ll> q;
int main() {
    scanf("%lld", &n);
    for(i=1;i<=n;i++) scanf("%lld%lld", &p[i].first, &p[i].second);
    sort(p+1, p+n+1, [&](pl& a, pl& b) {
        return a.first == b.first ? a.second > b.second : a.first > b.first;
    });
    for(i=2;i<=2000;i++) d[0][i] = -INF;
    for(i=1;i<=n;i++) {
        ll a = p[i].first;
        ll b = p[i].second;
        if(!a) break;
        for(ll j=2000;j>=0;j--) {
            d[i][j] = d[i-1][j];
            ll t = max(j - a + 1, 0LL);
            if(d[i-1][t] != -INF)
                d[i][j] = max(d[i][j], d[i-1][t] + b);
        }
    }
    ll t = i-1;
    for(;i<=n;i++) if(p[i].second > 0) q.push_back(p[i].second);
    ll r = -INF, s = 0;
    for(i=0;i<=2000;i++) {
        r = max(r, d[t][i] + s);
        if(i < q.size()) s += q[i];
    }
    printf("%lld", r);
    return 0;
}

Compilation message

straps.cpp: In function 'int main()':
straps.cpp:35:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i < q.size()) s += q[i];
              ^
straps.cpp:13:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &n);
                      ^
straps.cpp:14:67: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<=n;i++) scanf("%lld%lld", &p[i].first, &p[i].second);
                                                                   ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 33368 KB Output is correct
2 Correct 0 ms 33368 KB Output is correct
3 Correct 0 ms 33368 KB Output is correct
4 Correct 0 ms 33368 KB Output is correct
5 Correct 0 ms 33368 KB Output is correct
6 Correct 0 ms 33368 KB Output is correct
7 Correct 0 ms 33368 KB Output is correct
8 Correct 0 ms 33368 KB Output is correct
9 Correct 0 ms 33368 KB Output is correct
10 Correct 0 ms 33368 KB Output is correct
11 Correct 0 ms 33368 KB Output is correct
12 Correct 0 ms 33368 KB Output is correct
13 Correct 0 ms 33368 KB Output is correct
14 Correct 0 ms 33368 KB Output is correct
15 Correct 0 ms 33368 KB Output is correct
16 Correct 0 ms 33368 KB Output is correct
17 Correct 0 ms 33368 KB Output is correct
18 Correct 0 ms 33368 KB Output is correct
19 Correct 0 ms 33368 KB Output is correct
20 Correct 0 ms 33368 KB Output is correct
21 Correct 0 ms 33368 KB Output is correct
22 Correct 0 ms 33368 KB Output is correct
23 Correct 0 ms 33368 KB Output is correct
24 Correct 0 ms 33368 KB Output is correct
25 Correct 0 ms 33368 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 33368 KB Output is correct
2 Correct 0 ms 33368 KB Output is correct
3 Correct 0 ms 33368 KB Output is correct
4 Correct 0 ms 33368 KB Output is correct
5 Correct 0 ms 33368 KB Output is correct
6 Correct 0 ms 33368 KB Output is correct
7 Correct 0 ms 33368 KB Output is correct
8 Correct 0 ms 33368 KB Output is correct
9 Correct 0 ms 33368 KB Output is correct
10 Correct 0 ms 33368 KB Output is correct
11 Correct 0 ms 33368 KB Output is correct
12 Correct 0 ms 33368 KB Output is correct
13 Correct 3 ms 33368 KB Output is correct
14 Correct 0 ms 33368 KB Output is correct
15 Correct 3 ms 33368 KB Output is correct
16 Correct 0 ms 33368 KB Output is correct
17 Correct 0 ms 33368 KB Output is correct
18 Correct 0 ms 33368 KB Output is correct
19 Correct 0 ms 33368 KB Output is correct
20 Correct 0 ms 33368 KB Output is correct
21 Correct 0 ms 33368 KB Output is correct
22 Correct 0 ms 33368 KB Output is correct
23 Correct 0 ms 33368 KB Output is correct
24 Correct 0 ms 33368 KB Output is correct
25 Correct 0 ms 33368 KB Output is correct
26 Correct 0 ms 33368 KB Output is correct
27 Correct 0 ms 33368 KB Output is correct
28 Correct 0 ms 33368 KB Output is correct
29 Correct 9 ms 33368 KB Output is correct
30 Correct 6 ms 33368 KB Output is correct
31 Correct 13 ms 33368 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 33368 KB Output is correct
2 Correct 0 ms 33368 KB Output is correct
3 Correct 0 ms 33368 KB Output is correct
4 Correct 0 ms 33368 KB Output is correct
5 Correct 0 ms 33368 KB Output is correct
6 Correct 0 ms 33368 KB Output is correct
7 Correct 0 ms 33368 KB Output is correct
8 Correct 0 ms 33368 KB Output is correct
9 Correct 3 ms 33368 KB Output is correct
10 Correct 0 ms 33368 KB Output is correct
11 Correct 0 ms 33368 KB Output is correct
12 Correct 3 ms 33368 KB Output is correct
13 Correct 0 ms 33368 KB Output is correct
14 Correct 0 ms 33368 KB Output is correct
15 Correct 0 ms 33368 KB Output is correct
16 Correct 0 ms 33368 KB Output is correct
17 Correct 0 ms 33368 KB Output is correct
18 Correct 3 ms 33368 KB Output is correct
19 Correct 3 ms 33368 KB Output is correct
20 Correct 0 ms 33368 KB Output is correct
21 Correct 0 ms 33368 KB Output is correct
22 Correct 0 ms 33368 KB Output is correct
23 Correct 0 ms 33368 KB Output is correct
24 Correct 3 ms 33368 KB Output is correct
25 Correct 0 ms 33368 KB Output is correct
26 Correct 0 ms 33368 KB Output is correct
27 Correct 0 ms 33368 KB Output is correct
28 Correct 0 ms 33368 KB Output is correct
29 Correct 0 ms 33368 KB Output is correct
30 Correct 0 ms 33368 KB Output is correct
31 Correct 0 ms 33368 KB Output is correct
32 Correct 0 ms 33368 KB Output is correct
33 Correct 13 ms 33368 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 33368 KB Output is correct
2 Correct 0 ms 33368 KB Output is correct
3 Correct 0 ms 33368 KB Output is correct
4 Correct 0 ms 33368 KB Output is correct
5 Correct 0 ms 33368 KB Output is correct
6 Correct 0 ms 33368 KB Output is correct
7 Correct 0 ms 33368 KB Output is correct
8 Correct 0 ms 33368 KB Output is correct
9 Correct 0 ms 33368 KB Output is correct
10 Correct 0 ms 33368 KB Output is correct
11 Correct 0 ms 33368 KB Output is correct
12 Correct 0 ms 33368 KB Output is correct
13 Correct 0 ms 33368 KB Output is correct
14 Correct 0 ms 33368 KB Output is correct
15 Correct 0 ms 33368 KB Output is correct
16 Correct 0 ms 33368 KB Output is correct
17 Correct 0 ms 33368 KB Output is correct
18 Correct 0 ms 33368 KB Output is correct
19 Correct 3 ms 33368 KB Output is correct
20 Correct 13 ms 33368 KB Output is correct
21 Correct 13 ms 33368 KB Output is correct
22 Correct 6 ms 33368 KB Output is correct
23 Correct 6 ms 33368 KB Output is correct
24 Correct 0 ms 33368 KB Output is correct
25 Correct 0 ms 33368 KB Output is correct