oj.uz

Submission #525379

# Submission time Handle Problem Language Result Execution time Memory
525379 2022-02-11T13:46:57 Z TheKingAleks Skyline (IZhO11_skyline) C++14
100 / 100
 60 ms 48644 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 48452 KB Output is correct
2 Correct 24 ms 48440 KB Output is correct
3 Correct 24 ms 48408 KB Output is correct
4 Correct 25 ms 48452 KB Output is correct
5 Correct 30 ms 48452 KB Output is correct
6 Correct 30 ms 48460 KB Output is correct
7 Correct 25 ms 48536 KB Output is correct
8 Correct 24 ms 48448 KB Output is correct
9 Correct 25 ms 48456 KB Output is correct
10 Correct 29 ms 48564 KB Output is correct
11 Correct 38 ms 48484 KB Output is correct
12 Correct 25 ms 48508 KB Output is correct
13 Correct 28 ms 48440 KB Output is correct
14 Correct 31 ms 48512 KB Output is correct
15 Correct 52 ms 48520 KB Output is correct
16 Correct 58 ms 48440 KB Output is correct
17 Correct 59 ms 48524 KB Output is correct
18 Correct 60 ms 48644 KB Output is correct
19 Correct 52 ms 48524 KB Output is correct
20 Correct 56 ms 48460 KB Output is correct