Submission #8209

#	Time	Username	Problem	Language	Result	Execution time	Memory
8209		baneling100	스트랩 (JOI14_straps)	C++98	0 / 100	0 ms	1120 KiB

straps

#include <stdio.h>
#include <algorithm>
#define INF 0x7fffffff

using namespace std;

int N, M, A[2001], B[2001][2], D[2001], Ans=-INF;

void input(void) {

    int i, T, X, Y;

    scanf("%d",&T);
    for(i=1 ; i<=T ; i++) {
        scanf("%d %d",&X,&Y);
        if(X) {
            B[++M][0]=X-1;
            B[M][1]=Y;
        }
        else
            A[++N]=Y;
    }
    sort(A+1,A+N+1);
    for(i=N-1 ; i>=1 ; i--)
        A[i]+=A[i+1];
}

void process(void) {

    int i, j, k;

    for(i=2 ; i<=N ; i++)
        D[i]=-INF;
    for(i=1 ; i<=M ; i++)
        for(j=N ; j>=1 ; j--) {
            k=min(j+B[i][0],N);
            if(D[k]<D[j]+B[i][1] && D[j]!=-INF)
                D[k]=D[j]+B[i][1];
        }
    for(i=N-1 ; i>=0 ; i--)
        if(D[i]<D[i+1])
            D[i]=D[i+1];
    for(i=0 ; i<=N ; i++)
        if(Ans<D[i]+A[N-i+1])
            Ans=D[i]+A[N-i+1];
}

void output(void) {

    printf("%d",Ans);
}

int main(void) {

    input();
    process();
    output();

    return 0;
}

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