제출 #157209

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
157209		combi1k1	스트랩 (JOI14_straps)	C++14	100 / 100	27 ms	16120 KiB

straps

#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;
}

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