Submission #1249322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249322		nasjes	Discharging (NOI20_discharging)	C++20	0 / 100	56 ms	8260 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)/(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;
    for(int i=0; i<m; i++){
        dp[i]=min(get(g[i].fi), g[i].fi*n);
        len-=g[i].se;
        add({len, dp[i]});
    }
    cout<<dp[m-1]<<endl;
    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