Submission #525379

#	Time	Username	Problem	Language	Result	Execution time	Memory
525379		TheKingAleks	Skyline (IZhO11_skyline)	C++14	100 / 100	60 ms	48644 KiB

skyline

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAX_N = 302;
const int MAX_H = 202;
const int INF = 1e9+7;
int n, a[MAX_N], dp[MAX_N][MAX_H][MAX_H];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
    }
    for(int i=0; i<MAX_N; i++)
    {
        for(int j=0; j<MAX_H; j++)
        {
            for(int k=0; k<MAX_H; k++)
            {
                dp[i][j][k] = INF;
            }
        }
    }
    for(int i=a[1]; i>=0; i--)
    {
        dp[1][i][0] = (a[1]-i)*3;
    }
    for(int i=2; i<=n; i++)
    {
        for(int k=a[i-1]; k>=0; k--)
        {
            dp[i][a[i]][k] = min(dp[i][a[i]][k], dp[i-1][k][0]);
        }
        for(int j=a[i]; j>=0; j--)
        {
            for(int k=a[i-1]; k>=0; k--)
            {
                dp[i][j][k] = min(dp[i][j][k], dp[i][j+1][k] + 3);
            }
        }
        for(int j=a[i]-1; j>=0; j--)
        {
            for(int k=a[i-1]-1; k>=0; k--)
            {
                dp[i][j][k] = min(dp[i][j][k], dp[i][j+1][k+1] + 5);
            }
        }
        for(int tr=min({a[i-1],a[i],a[i+1]}); tr>=0; tr--)
        {
            for(int j=tr; j<=a[i]; j++)
            {
                dp[i+1][a[i+1]-tr][j-tr] = min(dp[i+1][a[i+1]-tr][j-tr], dp[i][j][tr] + 7*tr);
            }
        }
    }
    cout<<dp[n][0][0]<<endl;
}

• Subtask 1: 100 / 100