제출 #157209

#제출 시각아이디문제언어결과실행 시간메모리
157209combi1k1스트랩 (JOI14_straps)C++14
100 / 100
27 ms16120 KiB
#include<bits/stdc++.h>

using namespace std;

#define X   first
#define Y   second

const int   N   = 2002;
const int   inf = 2e9 + 7;

typedef pair<int,int>   ii;

int f[N][N];
ii  rope[N];

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;

    for(int i = 1 ; i <= n ; ++i)   {
        cin >> rope[i].X;
        cin >> rope[i].Y;
    }

    sort(rope + 1, rope + 1 + n,greater<ii>());

    for(int i = n ; i >= 1 ; --i)
    for(int j = 0 ; j <= n ; ++j)   {
        if (i > n)  {
            f[i][j] = 0;
            continue;
        }
        f[i][j] = max(f[i + 1][j],j > 0 ? f[i + 1][min(j - 1 + rope[i].X,n)] + rope[i].Y : 0);
    }

    cout << f[1][1] << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...