oj.uz

Submission #881081

# Submission time Handle Problem Language Result Execution time Memory
881081 2023-11-30T14:23:45 Z alexdd Skyline (IZhO11_skyline) C++17
100 / 100
 753 ms 51796 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++)
                {
                    int cnt2 = min(p,u) - cnt3;
                    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);

                    cnt2 = 0;
                    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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 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 12636 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 6 ms 6492 KB Output is correct
11 Correct 28 ms 25092 KB Output is correct
12 Correct 11 ms 6492 KB Output is correct
13 Correct 34 ms 29200 KB Output is correct
14 Correct 64 ms 35160 KB Output is correct
15 Correct 428 ms 47452 KB Output is correct
16 Correct 414 ms 41308 KB Output is correct
17 Correct 753 ms 51772 KB Output is correct
18 Correct 708 ms 51796 KB Output is correct
19 Correct 666 ms 49500 KB Output is correct
20 Correct 737 ms 51756 KB Output is correct