Submission #320660

#	Time	Username	Problem	Language	Result	Execution time	Memory
320660		saarang123	Discharging (NOI20_discharging)	C++14	0 / 100	244 ms	70880 KiB

Discharging

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int inf = 1e15;
signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);
    int n; cin >> n;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];
    vector<array<array<int, 4>, 2>> dp(n + 1);    //dp - cost, time, max, cnt
    for(int i = 0; i <= n; i++) dp[i][0] = dp[i][1] = {inf, inf, inf, inf};
    dp[1][0] = dp[1][1] = {a[1], 1, a[1], a[1]};
    for(int i = 2; i <= n; i++) {
        for(int j = 0; j < 2; j++) {
            int cost = dp[i - 1][j][0], cnt = dp[i - 1][j][3], mx = dp[i - 1][j][2], time = dp[i - 1][j][1];
            int ans = cost + time + a[i];
            dp[i][0] = min(dp[i][0], {ans, time + a[i], a[i], 1});
            int other = cost - cnt * time + (cnt + 1) * (time - mx + max(a[i], mx));
            dp[i][1] = min(dp[i][1], {other, time - mx + max(mx, a[i]), max(a[i], mx), cnt + 1});
        }
    }
    /*for(int i = 1; i <= n; i++) {
        cout << i << ": \n";
        for(int x : dp[i][0]) cout << x << ' '; cout << '\n';
        for(int x : dp[i][1]) cout << x << ' '; cout << '\n';
    }*/
    cout << min(dp[n][0][0], dp[n][1][0]) << '\n';
    return 0;
}

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