Submission #1091071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091071		pokmui9909	스트랩 (JOI14_straps)	C++17	100 / 100	29 ms	32088 KiB

straps

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define x first
#define y second

ll N; 
pair<ll, ll> A[2005];
ll D[2005][2005];

void chmax(ll &k, ll v){
    k = max(k, v);
}

int main(){
    cin.tie(0) -> sync_with_stdio(0);

    cin >> N;
    for(ll i = 1; i <= N; i++){
        cin >> A[i].x >> A[i].y;
    }
    sort(A + 1, A + N + 1, greater<pair<ll, ll>>());
    fill(D[0], D[2004] + 2005, -1e18);
    D[0][1] = 0;
    for(ll i = 0; i < N; i++){
        for(ll j = 0; j <= N; j++){
            chmax(D[i + 1][j], D[i][j]);
            if(j >= 1) chmax(D[i + 1][min(N, j - 1 + A[i + 1].x)], D[i][j] + A[i + 1].y);
        }
    }
    cout << *max_element(D[N], D[N] + N + 1);
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 45 / 45
• Subtask 4: 45 / 45