Submission #263329

#	Time	Username	Problem	Language	Result	Execution time	Memory
263329		FutymyClone	Discharging (NOI20_discharging)	C++14	47 / 100	1050 ms	91520 KiB

Discharging

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;

int n, a[N], rmq[20][N];
long long dp[N];
deque <int> dq;

int query (int u, int v) {
    int k = log2(v - u + 1);
    return max(rmq[k][u], rmq[k][v - (1 << k) + 1]);
}

long long cost (int j, int i) {
    if (j > n || i > n || j > i) return 0;
    return dp[j] + 1LL * query(j + 1, i) * (n - j);
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], rmq[0][i] = a[i];
    for (int k = 1; k < 20; k++) {
        for (int i = 1; i + (1 << k) - 1 <= n; i++) {
            rmq[k][i] = max(rmq[k - 1][i], rmq[k - 1][i + (1 << (k - 1))]);
        }
    }

    memset(dp, 0x3f, sizeof(dp)); dp[0] = 0;
    dq.push_back(0);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < dq.size(); j++) {
            dp[i] = min(dp[i], dp[dq[j]] + 1LL * query(dq[j] + 1, i) * (n - dq[j]));
        }
        //while (!dq.empty() && cost(dq.front(), i + 1) >= cost(i, i + 1)) dq.pop_front();
        while (!dq.empty() && dp[dq.back()] >= dp[i]) dq.pop_back();
        dq.push_back(i);
    }

    //for (int i = 1; i <= n; i++) cout << dp[i] << " ";
    //cout << "\n";
    cout << dp[n] << "\n";
    return 0;
}

Compilation message (stderr)

Discharging.cpp: In function 'int main()':
Discharging.cpp:34:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for (int j = 0; j < dq.size(); j++) {
      |                         ~~^~~~~~~~~~~

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