oj.uz

Submission #13269

# Submission time Handle Problem Language Result Execution time Memory
13269 2015-02-07T07:24:35 Z dohyun0324 Skyline (IZhO11_skyline) C++
100 / 100
 71 ms 37432 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 37432 KB Output is correct
2 Correct 0 ms 37432 KB Output is correct
3 Correct 0 ms 37432 KB Output is correct
4 Correct 2 ms 37432 KB Output is correct
5 Correct 0 ms 37432 KB Output is correct
6 Correct 0 ms 37432 KB Output is correct
7 Correct 0 ms 37432 KB Output is correct
8 Correct 0 ms 37432 KB Output is correct
9 Correct 3 ms 37432 KB Output is correct
10 Correct 4 ms 37432 KB Output is correct
11 Correct 11 ms 37432 KB Output is correct
12 Correct 3 ms 37432 KB Output is correct
13 Correct 12 ms 37432 KB Output is correct
14 Correct 26 ms 37432 KB Output is correct
15 Correct 50 ms 37432 KB Output is correct
16 Correct 43 ms 37432 KB Output is correct
17 Correct 71 ms 37432 KB Output is correct
18 Correct 65 ms 37432 KB Output is correct
19 Correct 63 ms 37432 KB Output is correct
20 Correct 64 ms 37432 KB Output is correct