Submission #169603

#	Time	Username	Problem	Language	Result	Execution time	Memory
169603		SamAnd	Skyline (IZhO11_skyline)	C++17	100 / 100	302 ms	108636 KiB

skyline

#include <bits/stdc++.h>
using namespace std;
const int N = 303, INF = 1000000009;

int n;
int a[N];

int dp[N][N][N];

int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    for (int i = 0; i <= n; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            for (int k = 0; k < N; ++k)
            {
                dp[i][j][k] = INF;
            }
        }
    }
    dp[1][0][a[1]] = 0;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = N - 1; j >= 0; --j)
        {
            for (int k = N - 1; k >= 0; --k)
            {
                if (k > 0)
                    dp[i][j][k - 1] = min(dp[i][j][k - 1], dp[i][j][k] + 3);
                if (k > 0 && j > 0)
                    dp[i][j - 1][k - 1] = min(dp[i][j - 1][k - 1], dp[i][j][k] + 5);
            }
        }
        if (i == n)
            break;
        for (int j = 0; j < N; ++j)
        {
            for (int k = 0; k < N; ++k)
            {
                if (a[i + 1] >= j && k >= j)
                {
                    dp[i + 1][k - j][a[i + 1] - j] = min(dp[i + 1][k - j][a[i + 1] - j], dp[i][j][k] + j * 7);
                }
            }
        }
    }
    printf("%d\n", dp[n][0][0]);
    return 0;
}

Compilation message (stderr)

skyline.cpp: In function 'int main()':
skyline.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
skyline.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~

• Subtask 1: 100 / 100