Submission #12873

#	Time	Username	Problem	Language	Result	Execution time	Memory
12873		tncks0121	스트랩 (JOI14_straps)	C++14	100 / 100	40 ms	1740 KiB

straps

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>
#include <iostream>

using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;

const int N_ = 2005;
const ll INF = (ll)1e15;
int N;

ll Table[2][N_+N_+50];
#define tb(i, j) Table[(i) & 1][(j) + N_]

ll ans;

void maximize (ll &t, ll v) {
    t = max(t, v);
}

int main() {
    scanf("%d", &N);
    
    for(int i = -N; i <= N; i++) tb(0, i) = -INF;
    tb(0, 0) = 0;
    
    int suma = 0;
    for(int r = 1; r <= N; r++) {
        int a, b; scanf("%d%d", &a, &b);
        for(int i = -N; i <= N; i++) tb(r, i) = tb(r-1, i);
        for(int x = -N; x <= N; x++) {
            int y = min(x + (a - 1), N);
            if(-N <= y && y <= N) maximize(tb(r, y), tb(r - 1, x) + b);
        }
    }
    
    for(int i = -1; i <= N; i++) ans = max(ans, tb(N, i));
    printf("%lld\n", ans);
    return 0;
}

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