Submission #751262

#	Time	Username	Problem	Language	Result	Execution time	Memory
751262		dsyz	Discharging (NOI20_discharging)	C++17	100 / 100	138 ms	33596 KiB

Discharging

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
struct ConvexHull {
	deque<pair<ll,ll> > dq;
	ll f(pair<ll,ll> line,ll x){
		return line.first * x + line.second;
	}
	ll query(ll x){
		while(dq.size() > 1){
			if(f(dq[0],x) < f(dq[1],x)){
				dq.pop_front();
			}else{
				break;
			}
		}
		return f(dq[0],x);
	}
	long double Intersect(ll a,ll b,ll c,ll d){
		return (long double)(d - b) / (a - c);
	}
	long double intersect(pair<ll,ll> p1,pair<ll,ll> p2){
		return Intersect(p1.first,p1.second,p2.first,p2.second);
	}
	void ins(ll m,ll c){
		pair<ll,ll> line = make_pair(m,c);
		while(dq.size() > 1){
			ll s = dq.size();
			if(intersect(dq[s - 1],line) <= intersect(dq[s - 2],line)){
				dq.pop_back();
			}else{
				break;
			}
		}
		dq.push_back(line);
	}
} CH; //returns maximum y
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N;
	cin>>N;
	ll T[N + 1];
	for(ll i = 1;i <= N;i++){
		cin>>T[i];
	}
	T[0] = 0;
	ll premaxT[N + 1];
	premaxT[0] = 0;
	for(ll i = 1;i <= N;i++){
		premaxT[i] = max(premaxT[i - 1],T[i]);
	}
	ll dp[N + 1];
	dp[0] = 0;
	CH.dq.clear();
	CH.ins(-N,0);
	for(ll i = 1;i <= N;i++){
		if(premaxT[i - 1] < T[i]){
			dp[i] = -CH.query(T[i]);
			ll ptr = i;
			while(ptr < N && T[ptr] <= T[i]){
				ptr++;
			}
			CH.ins(ptr - N - 1,-dp[i]);
		}else{
			dp[i] = dp[i - 1];
		}
	}
	cout<<dp[N]<<'\n';
}

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