oj.uz

Submission #8218

# Submission time Handle Problem Language Result Execution time Memory
8218 2014-09-07T05:39:28 Z baneling100 스트랩 (JOI14_straps) C++
100 / 100
 0 ms 1120 KB 
#include <stdio.h>
#include <algorithm>
#define INF 0x7fffffff

using namespace std;

int T, N, M, A[2001], B[2001][2], D[2001], Ans, Sum, Cnt=1;

void input(void) {

    int i, X, Y;

    scanf("%d",&T);
    for(i=1 ; i<=T ; i++) {
        scanf("%d %d",&X,&Y);
        if(X) {
            if(Y>=0) {
                Sum+=Y;
                Cnt+=X-1;
            }
            else
                if(X>=2) {
                    B[++M][0]=X-1;
                    B[M][1]=Y;
                }
        }
        else
            if(Y>0)
                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=1 ; i<=N-1 ; i++)
        D[i]=-INF;
    for(i=1 ; i<=M ; i++)
        for(j=N-1 ; j>=0 ; j--)
            if(D[j]!=-INF) {
                k=min(j+B[i][0],N-1);
                if(D[k]<D[j]+B[i][1])
                    D[k]=D[j]+B[i][1];
            }
    for(i=N-2 ; i>=0 ; i--)
        if(D[i]<D[i+1])
            D[i]=D[i+1];
    Ans=Sum;
    for(i=1 ; i<=N ; i++) {
        if(i<=Cnt) {
            if(Ans<Sum+A[N-i+1])
                Ans=Sum+A[N-i+1];
        }
        else
            if(Ans<Sum+D[i-Cnt]+A[N-i+1])
                Ans=Sum+D[i-Cnt]+A[N-i+1];
    }
}

void output(void) {

    printf("%d",Ans);
}

int main(void) {

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

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1120 KB Output is correct
2 Correct 0 ms 1120 KB Output is correct
3 Correct 0 ms 1120 KB Output is correct
4 Correct 0 ms 1120 KB Output is correct
5 Correct 0 ms 1120 KB Output is correct
6 Correct 0 ms 1120 KB Output is correct
7 Correct 0 ms 1120 KB Output is correct
8 Correct 0 ms 1120 KB Output is correct
9 Correct 0 ms 1120 KB Output is correct
10 Correct 0 ms 1120 KB Output is correct
11 Correct 0 ms 1120 KB Output is correct
12 Correct 0 ms 1120 KB Output is correct
13 Correct 0 ms 1120 KB Output is correct
14 Correct 0 ms 1120 KB Output is correct
15 Correct 0 ms 1120 KB Output is correct
16 Correct 0 ms 1120 KB Output is correct
17 Correct 0 ms 1120 KB Output is correct
18 Correct 0 ms 1120 KB Output is correct
19 Correct 0 ms 1120 KB Output is correct
20 Correct 0 ms 1120 KB Output is correct
21 Correct 0 ms 1120 KB Output is correct
22 Correct 0 ms 1120 KB Output is correct
23 Correct 0 ms 1120 KB Output is correct
24 Correct 0 ms 1120 KB Output is correct
25 Correct 0 ms 1120 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1120 KB Output is correct
2 Correct 0 ms 1120 KB Output is correct
3 Correct 0 ms 1120 KB Output is correct
4 Correct 0 ms 1120 KB Output is correct
5 Correct 0 ms 1120 KB Output is correct
6 Correct 0 ms 1120 KB Output is correct
7 Correct 0 ms 1120 KB Output is correct
8 Correct 0 ms 1120 KB Output is correct
9 Correct 0 ms 1120 KB Output is correct
10 Correct 0 ms 1120 KB Output is correct
11 Correct 0 ms 1120 KB Output is correct
12 Correct 0 ms 1120 KB Output is correct
13 Correct 0 ms 1120 KB Output is correct
14 Correct 0 ms 1120 KB Output is correct
15 Correct 0 ms 1120 KB Output is correct
16 Correct 0 ms 1120 KB Output is correct
17 Correct 0 ms 1120 KB Output is correct
18 Correct 0 ms 1120 KB Output is correct
19 Correct 0 ms 1120 KB Output is correct
20 Correct 0 ms 1120 KB Output is correct
21 Correct 0 ms 1120 KB Output is correct
22 Correct 0 ms 1120 KB Output is correct
23 Correct 0 ms 1120 KB Output is correct
24 Correct 0 ms 1120 KB Output is correct
25 Correct 0 ms 1120 KB Output is correct
26 Correct 0 ms 1120 KB Output is correct
27 Correct 0 ms 1120 KB Output is correct
28 Correct 0 ms 1120 KB Output is correct
29 Correct 0 ms 1120 KB Output is correct
30 Correct 0 ms 1120 KB Output is correct
31 Correct 0 ms 1120 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1120 KB Output is correct
2 Correct 0 ms 1120 KB Output is correct
3 Correct 0 ms 1120 KB Output is correct
4 Correct 0 ms 1120 KB Output is correct
5 Correct 0 ms 1120 KB Output is correct
6 Correct 0 ms 1120 KB Output is correct
7 Correct 0 ms 1120 KB Output is correct
8 Correct 0 ms 1120 KB Output is correct
9 Correct 0 ms 1120 KB Output is correct
10 Correct 0 ms 1120 KB Output is correct
11 Correct 0 ms 1120 KB Output is correct
12 Correct 0 ms 1120 KB Output is correct
13 Correct 0 ms 1120 KB Output is correct
14 Correct 0 ms 1120 KB Output is correct
15 Correct 0 ms 1120 KB Output is correct
16 Correct 0 ms 1120 KB Output is correct
17 Correct 0 ms 1120 KB Output is correct
18 Correct 0 ms 1120 KB Output is correct
19 Correct 0 ms 1120 KB Output is correct
20 Correct 0 ms 1120 KB Output is correct
21 Correct 0 ms 1120 KB Output is correct
22 Correct 0 ms 1120 KB Output is correct
23 Correct 0 ms 1120 KB Output is correct
24 Correct 0 ms 1120 KB Output is correct
25 Correct 0 ms 1120 KB Output is correct
26 Correct 0 ms 1120 KB Output is correct
27 Correct 0 ms 1120 KB Output is correct
28 Correct 0 ms 1120 KB Output is correct
29 Correct 0 ms 1120 KB Output is correct
30 Correct 0 ms 1120 KB Output is correct
31 Correct 0 ms 1120 KB Output is correct
32 Correct 0 ms 1120 KB Output is correct
33 Correct 0 ms 1120 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1120 KB Output is correct
2 Correct 0 ms 1120 KB Output is correct
3 Correct 0 ms 1120 KB Output is correct
4 Correct 0 ms 1120 KB Output is correct
5 Correct 0 ms 1120 KB Output is correct
6 Correct 0 ms 1120 KB Output is correct
7 Correct 0 ms 1120 KB Output is correct
8 Correct 0 ms 1120 KB Output is correct
9 Correct 0 ms 1120 KB Output is correct
10 Correct 0 ms 1120 KB Output is correct
11 Correct 0 ms 1120 KB Output is correct
12 Correct 0 ms 1120 KB Output is correct
13 Correct 0 ms 1120 KB Output is correct
14 Correct 0 ms 1120 KB Output is correct
15 Correct 0 ms 1120 KB Output is correct
16 Correct 0 ms 1120 KB Output is correct
17 Correct 0 ms 1120 KB Output is correct
18 Correct 0 ms 1120 KB Output is correct
19 Correct 0 ms 1120 KB Output is correct
20 Correct 0 ms 1120 KB Output is correct
21 Correct 0 ms 1120 KB Output is correct
22 Correct 0 ms 1120 KB Output is correct
23 Correct 0 ms 1120 KB Output is correct
24 Correct 0 ms 1120 KB Output is correct
25 Correct 0 ms 1120 KB Output is correct