Submission #302383

#	Time	Username	Problem	Language	Result	Execution time	Memory
302383		errorgorn	Discharging (NOI20_discharging)	C++14	100 / 100	171 ms	22952 KiB

Discharging

#include <bits/stdc++.h>

using namespace std;



#define ll long long

#define ii pair<int,int>

#define fi first

#define se second

#define endl '\n'



#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);(s<e?x++:x--))

#define sz(x) (int) (x).size()

#define all(x) (x).begin(),(x).end()



struct line{

	ll m,c;

	

	line (ll _m,ll _c){

		m=_m,c=_c;

	}

	

	ll get(ll x){

		return m*x+c;

	}

};



struct LCH{	

	deque<line> dq;

	

	double POI(line i,line j){

		return (double)(i.c-j.c)/(double)(j.m-i.m);

	}

	

	void insert(line i){

		//cout<<"debug: "<<i.m<<" "<<i.c<<endl;

		

		while (sz(dq)>=2 && POI(dq.back(),i)<POI(dq[sz(dq)-2],dq.back())) dq.pop_back();

		dq.push_back(i);

		

		//for (auto &it:dq) cout<<it.m<<"_"<<it.c<<" ";cout<<endl;

	}

	

	ll query(ll x){

		while (sz(dq)>=2 && POI(dq[0],dq[1])<x) dq.pop_front();

		

		return dq.front().get(x);

	}

} hull=LCH();



int n;

ll arr[1000005];

vector<ii> v;



int main(){

	cin.tie(0);

	cout.tie(0);

	ios::sync_with_stdio(false);

	

	cin>>n;

	rep(x,0,n){

		cin>>arr[x];

		if (v.empty() || v.back().fi<arr[x]){

			v.push_back(ii(arr[x],1));

		}

		else{

			v.back().se++;

		}

	}

	

	ll pw=0;

	

	//for (auto &it:v) cout<<it.fi<<" "<<it.se<<endl;

	

	for (auto &it:v) pw+=it.se;

	

	hull.insert(line(pw,0));

	

	ll ans=0;

	for (auto &it:v){

		ans=hull.query(it.fi);

		

		//cout<<ans<<endl;

		pw-=it.se;

		hull.insert(line(pw,ans));

	}

	

	cout<<ans<<endl;

}

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