Submission #21177

#	Time	Username	Problem	Language	Result	Execution time	Memory
21177		junodeveloper	스트랩 (JOI14_straps)	C++14	100 / 100	33 ms	33368 KiB

straps

#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(int j=2000;j>=0;j--) {
            d[i][j] = d[i-1][j];
            if(j < 2000) d[i][j] = max(d[i][j], d[i][j+1]);
            if(j - a + 1 >= 0 && d[i-1][j-a+1] != -INF)
                d[i][j] = max(d[i][j], d[i-1][j-a+1] + 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 (stderr)

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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 45 / 45
• Subtask 4: 45 / 45