oj.uz

Submission #320660

# Submission time Handle Problem Language Result Execution time Memory
320660 2020-11-09T12:41:42 Z saarang123 Discharging (NOI20_discharging) C++14
0 / 100
 244 ms 70880 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 244 ms 70880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -