Submission #13269

#	Time	Username	Problem	Language	Result	Execution time	Memory
13269		dohyun0324	Skyline (IZhO11_skyline)	C++98	100 / 100	71 ms	37432 KiB

skyline

#include<stdio.h>
#include<algorithm>
#define M 2147483647
using namespace std;
int dap=M,n,a[310],d[210][210][210],mini[210][210];
int main()
{
    int i,j,k,l;
    scanf("%d",&n);
    for(i=1;i<=n;i++) scanf("%d",&a[i]);
    for(i=1;i<=n;i++){
        if(i==1) d[a[i]][0][0]=a[i]*3;
        else{
            for(j=0;j<=a[i];j++){
                for(k=0;k<=a[i]-j;k++){
                    l=a[i]-j-k;
                    if(i==1 && k) continue;
                    if(i<=2 && l) continue;
                    d[j][k][l]=0;
                    if(mini[k][l]!=M) d[j][k][l]=3*j+2*k+2*l+mini[k][l];
                    if(d[j][k][l] && i==n && dap>d[j][k][l]) dap=d[j][k][l];
                }
            }
        }
        for(j=0;j<=201;j++){
            for(k=0;k<=201;k++){
                mini[j][k]=M;
            }
        }
        for(j=a[i];j>=0;j--){
            for(k=a[i]-j;k>=0;k--){
                mini[j][k]=min(mini[j+1][k],mini[j][k+1]);
                l=a[i]-j-k;
                if(d[j][k][l] && mini[j][k]>d[j][k][l]) mini[j][k]=d[j][k][l];
            }
        }
    }
    if(n==1) printf("%d",3*a[1]);
    else printf("%d",dap);
    return 0;
}

• Subtask 1: 100 / 100