Submission #12018

#	Time	Username	Problem	Language	Result	Execution time	Memory
12018		dohyun0324	도장 모으기 (JOI14_stamps)	C++98	100 / 100	84 ms	71916 KiB

stamps

#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 / 10
• Subtask 2: 75 / 75
• Subtask 3: 15 / 15