Submission #1249288

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249288		nasjes	Discharging (NOI20_discharging)	C++20	11 / 100	58 ms	8264 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];
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);
    }
    sort(g.begin(), g.end());
    ll sz=0;
    ll len=g.size();
    for(int i=0; i<len-1; i++){
        ll mx1=g[i].fi;
        ll gs=g[i].se;
        sz+=gs;
        ll mx2=g[i+1].fi;
        if((mx2-mx1)*gs<=(mx1*(n-sz))){
            g[i].fi=0;
            g[i+1].se+=g[i].se;
        }
    }
    vector<pll> res;
    for(int i=0; i<len; i++){
        if(g[i].fi==0)continue;
        res.pb(g[i]);
    }
    len=res.size();
    ll ans=0;
    ll wait=0;
    for(auto x: res){
        ans+=((x.fi+wait))*(x.se);
        wait+=x.fi;
    }
    cout<<ans<<endl;
    return 0;
}

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