Submission #873924

#	Time	Username	Problem	Language	Result	Execution time	Memory
873924		noiaint	Discharging (NOI20_discharging)	C++17	100 / 100	113 ms	25976 KiB

Discharging

#include <bits/stdc++.h>
#define int long long
#define double long double
 
using namespace std;
 
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()
 
#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1 << (x))
#define popcount __builtin_popcountll
 
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
long long rand(long long l, long long r) {
    return l + rd() % (r - l + 1);
}
 
const int N = 1e6 + 5;
const int mod = 1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int inf = 1e9; // INT_MAX;
const long long llinf = 1e18; // LLONG_MAX;
 
template<class X, class Y>
bool minimize(X &a, Y b) {
    return a > b ? (a = b, true) : false;
}
 
template<class X, class Y>
bool maximize(X &a, Y b) {
    return a < b ? (a = b, true) : false;
}
 
template<class X, class Y>
bool add(X &a, Y b) {
    a += b;
    while (a >= mod) a -= mod;
    while (a < 0) a += mod;
    return true;
}
 
int n;
int a[N];
int f[N];
 
double F(int j, int k) {
    return (f[j] - f[k]) / (j - k);
}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        a[i] = max(a[i], a[i - 1]);
    }
 
    memset(f, 0, sizeof f);
    f[0] = 0;
 
    deque<int> q;
    q.push_back(0);
    for (int i = 1; i <= n; ++i) {
        while (q.size() >= 2 && F(q[0], q[1]) < a[i]) q.pop_front();
        int j = q.front();
        f[i] = a[i] * (n - j) + f[j];
        while (q.size() >= 2 && F(q[q.size() - 2], q[q.size() - 1]) > F(q[q.size() - 1], i)) q.pop_back();
        q.push_back(i);
    }
 
    cout << f[n];
 
    return 0;
}
 
/*
5
1 3 2 6 3
27
 
7
1 1 2 2 2 2 2
14
*/

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