oj.uz

Submission #881076

# Submission time Handle Problem Language Result Execution time Memory
881076 2023-11-30T14:19:02 Z alexdd Skyline (IZhO11_skyline) C++17
0 / 100
 98 ms 12792 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 6 ms 12792 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 2 ms 2392 KB Output is correct
8 Correct 5 ms 2396 KB Output is correct
9 Correct 25 ms 4440 KB Output is correct
10 Incorrect 98 ms 6488 KB Output isn't correct
11 Halted 0 ms 0 KB -