Submission #525150

#	Time	Username	Problem	Language	Result	Execution time	Memory
525150		TheKingAleks	Skyline (IZhO11_skyline)	C++14	0 / 100	1 ms	716 KiB

skyline

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

• Subtask 1: 0 / 100