Submission #881076

#	Time	Username	Problem	Language	Result	Execution time	Memory
881076		alexdd	Skyline (IZhO11_skyline)	C++17	0 / 100	98 ms	12792 KiB

skyline

#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
const int INF = 1e9;
int n;
int dp[315][205][205];
int h[315];
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>h[i];
    }
    for(int i=1;i<=n+2;i++)
        for(int u=0;u<=200;u++)
            for(int j=0;j<=200;j++)
                dp[i][u][j]=INF;
    dp[2][h[1]][h[2]]=0;
    for(int i=2;i<=n+1;i++)
    {
        for(int j=0;j<=200;j++)
        {
            for(int k=0;k<=200;k++)
            {
                int p=j,u=k;
                if(dp[i][p][u]==INF)
                    continue;
                for(int cnt3=0;cnt3<=min(h[i+1],min(p,u));cnt3++)
                {
                    if(min(cnt3,p-cnt3)>50)
                        continue;
                    for(int cnt2=0;cnt2+cnt3<=min(p,u);cnt2++)
                    {
                        dp[i+1][u-cnt2-cnt3][h[i+1]-cnt3] = min(dp[i+1][u-cnt2-cnt3][h[i+1]-cnt3], dp[i][p][u] + (p-cnt2-cnt3)*3 + cnt2*5 + cnt3*7);
                    }
                }
                /*int nxt = h[i+1];
                int cnt3 = min({p,u,nxt});
                p -= cnt3;
                u -= cnt3;
                nxt -= cnt3;
                int cnt2 = min(p,u);
                p -= cnt2;
                u -= cnt2;
                int cnt1 = p;
                p -= cnt1;
                dp[i+1][u][nxt] = min(dp[i+1][u][nxt], dp[i][j][k] + cnt1*3 + cnt2*5 + cnt3*7);

                p=j;
                u=k;
                nxt=h[i+1];
                cnt2 = min(p,u);
                p -= cnt2;
                u -= cnt2;
                cnt1 = p;
                p -= cnt1;
                dp[i+1][u][nxt] = min(dp[i+1][u][nxt], dp[i][j][k] + cnt1*3 + cnt2*5);

                p=j;
                u=k;
                cnt1 = p;
                p -= cnt1;
                dp[i+1][u][nxt] = min(dp[i+1][u][nxt], dp[i][j][k] + cnt1*3);*/
            }
        }
    }
    cout<<min({dp[n][0][0],dp[n+1][0][0],dp[n+2][0][0]});
    return 0;
}
/**

dp[i][p][u] = costul minim pentru a construi toate cladirile 1..i-2, iar cladirea i-1 sa mai aiba nevoie de p inaltime, iar cladirea i de u inaltime
dp[i+1][

dp[i][p][u] = min(dp[i-1][])

*/

• Subtask 1: 0 / 100