Submission #345883

#	Time	Username	Problem	Language	Result	Execution time	Memory
345883		nicolaalexandra	Skyline (IZhO11_skyline)	C++14	100 / 100	115 ms	51308 KiB

skyline

#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 / 100