Submission #1249323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249323		nasjes	Discharging (NOI20_discharging)	C++20	100 / 100	226 ms	65292 KiB

Discharging

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
const ll dim = 2*(1e6)+7;
//const ll mod = 1e9 + 7;
const ll inf = 1e17 + 77;
#define endl "\n"
#define fi first
#define pb push_back
#define se second
#define vll vector<ll>

ll n, m, k;
ll a[dim], dp[dim];
deque<pll> dq;

ld cross(pll p1, pll p2){
    return (ld)((p1.se-p2.se)/(ld)(p2.fi-p1.fi));
}
void add(pll cur){
    while(dq.size()>=2 && cross(dq[dq.size()-2], cur)>=cross(dq[dq.size()-1], cur)){
        dq.pop_back();
    }
    dq.push_back(cur);
}
ll get(ll x){
    while(dq.size()>1 && cross(dq[1], dq[0])<x)dq.pop_front();
    pll cur=dq.front();
    return cur.fi*x+cur.se;
}
int main() {

    ll  u, w,q,   v, y;
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>a[i];
    }
    ll mx=0;
    map<ll, ll> mp;
    for(int i=1; i<=n; i++){
        mx=max(mx, a[i]);
        a[i]=mx;
        mp[a[i]]++;
    }
    vector<pll> g;
    for(auto x: mp){
        g.pb(x);
    }
    m=g.size();
    ll len=n;
    add({n, 0});
    for(int i=0; i<m; i++){
        dp[i]=get(g[i].fi);
        len-=g[i].se;
        add({len, dp[i]});
    }
    cout<<dp[m-1]<<endl;
    return 0;
}

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