Submission #1092169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092169		ByeWorld	Discharging (NOI20_discharging)	C++14	100 / 100	272 ms	45324 KiB

Discharging

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<ll,ll> pii;
typedef pair<ll,pii> ipii;
const int MAXN = 1e6+10;
const ll INF = 1e18+10;
const int MOD = 998244353;
const int LOG = 20;
const int ADD = 1e10;

int n, x;
int a[MAXN];
vector <pii> vec;
int dp[MAXN], cnt[MAXN], val[MAXN];
int pr[MAXN];

struct Line {
	int m, c;
	int getY(int x){
		return m*x+c;
	}
	pii cut(Line oth){
		return pii(oth.c-c, m-oth.m);
	}
};
vector <Line> ch;

bool cek(Line a, Line b, Line c){
	int A = b.cut(a).fi, B = b.cut(a).se;
	int C = c.cut(b).fi, D = c.cut(b).se;
	// A/B < C/D
	if(A/B == C/D){
		return (A%B)*D > (C%D)*B;
	}
	return A/B > C/D;
}
void add(Line nw){
	while(ch.size()>=2 && 
		!cek(ch[ch.size()-2], ch.back(), nw) ) ch.pop_back();
	ch.pb(nw);
	// for(auto in : ch) cout << in.m << ' ' << in.c << " mc\n";
	// 	cout << "done\n";
}
int que(int x){
	if(ch.size() == 1) return ch[0].getY(x);

	int l=1, r=ch.size()-1, mid=0, cnt=INF;
	while(r-l>=5){
		mid = md;
		int le = ch[mid-1].getY(x), ri = ch[mid].getY(x);
		cnt = min(cnt, min(le, ri));
		if(le > ri) l = mid+2;
		else r = mid-2;
	}
	for(int i=max(0ll,l-1); i<=min(r+1,(int)ch.size()-1); i++) 
		cnt = min(cnt, ch[i].getY(x));
	return cnt;
}
signed main(){
	cin >> n;
	for(int i=1; i<=n; i++) cin >> a[i];
	vec.pb({-1,-1});
	for(int i=1; i<=n; i++){
		int te = a[i], id = i;
		while(i+1<=n && te>=a[i+1]) i++;
		vec.pb({te, i-id+1});
	}
	n = vec.size()-1;
	for(int i=1; i<=n; i++){
		val[i] = vec[i].fi, cnt[i] = vec[i].se;
		pr[i] = pr[i-1] + cnt[i];
	}
	
	for(int i=1; i<=n; i++) dp[i] = INF;
	Line nw; nw.m = -val[n]; nw.c = val[n]*pr[n];
	add(nw);

	for(int i=n; i>=1; i--){
		dp[i] = que(pr[i-1]);

		Line nw; nw.m = -val[i-1]; nw.c = dp[i] + val[i-1]*pr[n];
		add(nw);
	}
	// for(int i=n; i>=1; i--){
	// 	for(int j=i; j<=n; j++){
	// 		dp[i] = min(dp[i], dp[j+1] + val[j]*pr[n] - val[j]*pr[i-1]);
	// 	}
	// }
	cout << dp[1] << '\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