oj.uz

Submission #12018

# Submission time Handle Problem Language Result Execution time Memory
12018 2014-12-17T16:35:34 Z dohyun0324 도장 모으기 (JOI14_stamps) C++
100 / 100
 84 ms 71916 KB 
#include<stdio.h>
int n,t;
int a[3010],b[3010],c[3010],d[3010];
long long dp[3010][3010];
int main()
{
    int i,j,g,h;
    long long s;
    scanf("%d %d",&n,&t);
    for(i=1;i<=n;i++){
        scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);
    }
    for(i=0;i<=n;i++){
        for(j=0;j<=n;j++){
            dp[i][j]=(long long)2147483647*(long long)2147483647;
        }
    }
    dp[0][0]=t;
    for(i=1;i<=n;i++)
    {
        for(j=0;j<=n;j++)
        {
             dp[i][j]=dp[i-1][j]+a[i]+b[i]+t*(j*2+1);
             if(j && dp[i][j]>dp[i-1][j]+c[i]+d[i]+t*(j*2+1)) dp[i][j]=dp[i-1][j]+c[i]+d[i]+t*(j*2+1);
             if(dp[i][j]>dp[i-1][j+1]+a[i]+d[i]+t*(j*2+1)) dp[i][j]=dp[i-1][j+1]+a[i]+d[i]+t*(j*2+1);
             if(j && dp[i][j]>s+t*(j*2+1)) dp[i][j]=s+t*(j*2+1);
             if(j==0 || s>dp[i-1][j]) s=dp[i-1][j];
             s+=b[i]+c[i];
        }
    }
    printf("%lld",dp[n][0]);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 71916 KB Output is correct
2 Correct 0 ms 71916 KB Output is correct
3 Correct 0 ms 71916 KB Output is correct
4 Correct 0 ms 71916 KB Output is correct
5 Correct 0 ms 71916 KB Output is correct
6 Correct 0 ms 71916 KB Output is correct
7 Correct 0 ms 71916 KB Output is correct
8 Correct 0 ms 71916 KB Output is correct
9 Correct 0 ms 71916 KB Output is correct
10 Correct 0 ms 71916 KB Output is correct
11 Correct 0 ms 71916 KB Output is correct
12 Correct 0 ms 71916 KB Output is correct
13 Correct 0 ms 71916 KB Output is correct

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 71916 KB Output is correct
2 Correct 0 ms 71916 KB Output is correct
3 Correct 0 ms 71916 KB Output is correct
4 Correct 0 ms 71916 KB Output is correct
5 Correct 0 ms 71916 KB Output is correct
6 Correct 0 ms 71916 KB Output is correct
7 Correct 0 ms 71916 KB Output is correct
8 Correct 0 ms 71916 KB Output is correct
9 Correct 0 ms 71916 KB Output is correct
10 Correct 0 ms 71916 KB Output is correct
11 Correct 0 ms 71916 KB Output is correct
12 Correct 0 ms 71916 KB Output is correct
13 Correct 0 ms 71916 KB Output is correct
14 Correct 0 ms 71916 KB Output is correct
15 Correct 0 ms 71916 KB Output is correct
16 Correct 0 ms 71916 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 71916 KB Output is correct
2 Correct 0 ms 71916 KB Output is correct
3 Correct 76 ms 71916 KB Output is correct
4 Correct 64 ms 71916 KB Output is correct
5 Correct 44 ms 71916 KB Output is correct
6 Correct 20 ms 71916 KB Output is correct
7 Correct 8 ms 71916 KB Output is correct
8 Correct 72 ms 71916 KB Output is correct
9 Correct 72 ms 71916 KB Output is correct
10 Correct 76 ms 71916 KB Output is correct
11 Correct 68 ms 71916 KB Output is correct
12 Correct 76 ms 71916 KB Output is correct
13 Correct 72 ms 71916 KB Output is correct
14 Correct 68 ms 71916 KB Output is correct
15 Correct 72 ms 71916 KB Output is correct
16 Correct 72 ms 71916 KB Output is correct
17 Correct 84 ms 71916 KB Output is correct