Submission #335746

#	Time	Username	Problem	Language	Result	Execution time	Memory
335746		mihai145	Discharging (NOI20_discharging)	C++14	36 / 100	1092 ms	18028 KiB

Discharging

#include <iostream>

using namespace std;

const long long INF = (1LL << 60);
const int NMAX = 1e6;

int N;
long long T[NMAX + 5], dp[NMAX + 5];

int main()
{
    // The following line disables syncing between cin/scanf and cout/printf.
    // It makes input faster, but you must not use functions from <cstdio> (e.g. scanf/printf) directly.
    // This line must be executed before any use of cin/cout.
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    // Your code goes here ...
    // (You can now read input and write output normally using cin/cout.)

    cin >> N;

    for(int i = 1; i <= N; i++)
        cin >> T[i];

    dp[N + 1] = 0;

    for(int i = N; i >= 1; i--)
    {
        dp[i] = INF;

        long long maxi = 0;
        for(int j = i; j <= N; j++)
        {
            maxi = max(maxi, T[j]);
            dp[i] = min(dp[i], maxi * (N - i + 1) + dp[j + 1]);
        }
    }

    cout << dp[1] << '\n';

    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 13 / 13
• Subtask 3: 0 / 25
• Subtask 4: 0 / 11
• Subtask 5: 14 / 14
• Subtask 6: 0 / 28