oj.uz

Submission #345883

# Submission time Handle Problem Language Result Execution time Memory
345883 2021-01-08T11:33:48 Z nicolaalexandra Skyline (IZhO11_skyline) C++14
100 / 100
 115 ms 51308 KB 
#include <bits/stdc++.h>
#define DIM 310
#define DIMM 210
#define INF 1000000000
using namespace std;

int dp[DIM][DIMM][DIMM],v[DIM];
int n,i,j,k,maxi;

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n;
    for (i=1;i<=n;i++){
        cin>>v[i];
        maxi = max (maxi,v[i]);
    }

    /// dp[i][j][k] - costul minim sa ajung in i si ultimele 2 sa fie j,k si in rest 0

    for (i=1;i<=n;i++)
        for (j=0;j<=maxi+1;j++)
            for (k=0;k<=maxi+1;k++)
                dp[i][j][k] = INF;

    for (i=0;i<=v[1];i++)
        dp[2][v[2]][i] = dp[1][i][0] = 3*(v[1]-i);

    for (i=2;i<=n;i++){

        /// aplic doar prima si a doua operatie
        for (j=maxi;j>=0;j--)
            for (k=maxi;k>=0;k--){
                dp[i][j][k] = min (dp[i][j][k],dp[i][j+1][k]+3);
                dp[i][j][k] = min (dp[i][j][k],dp[i][j+1][k+1]+5);
            }

        if (i == n)
            continue;

        /// nu are sens sa folosesc alta operatie in afara de a treia pt ca le am folosit deja
        for (j=maxi;j>=0;j--)
            for (k=maxi;k>=0;k--)
                if (k <= j && k <= v[i+1])
                    dp[i+1][v[i+1]-k][j-k] = min (dp[i+1][v[i+1]-k][j-k],dp[i][j][k]+7*k);

    }

    cout<<dp[n][0][0];


    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 1260 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 2 ms 748 KB Output is correct
8 Correct 1 ms 876 KB Output is correct
9 Correct 4 ms 2412 KB Output is correct
10 Correct 7 ms 4076 KB Output is correct
11 Correct 46 ms 24044 KB Output is correct
12 Correct 10 ms 5356 KB Output is correct
13 Correct 55 ms 28396 KB Output is correct
14 Correct 65 ms 33644 KB Output is correct
15 Correct 104 ms 46956 KB Output is correct
16 Correct 94 ms 42220 KB Output is correct
17 Correct 114 ms 51308 KB Output is correct
18 Correct 114 ms 50924 KB Output is correct
19 Correct 110 ms 49132 KB Output is correct
20 Correct 115 ms 51308 KB Output is correct