Submission #498712

#	Time	Username	Problem	Language	Result	Execution time	Memory
498712		jiahng	Discharging (NOI20_discharging)	C++14	11 / 100	304 ms	149168 KiB

Discharging

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll
typedef pair<int,int> pi;
typedef vector <ll> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0)
#define MOD 1000000007
#define maxn 1000010
#define INF (ll)1e18

int N;
int dp[maxn], T[maxn];
int f(pi line, int x){
	if (line == pi(-1,-1)) return INF;
	return line.f * x + line.s;
}

ld intersect(pi line1, pi line2){
	return (line2.s - line1.s) / (line1.f - line2.f);
}

struct node{
	int s,e,m;
	node *l,*r;
	pi val = pi(-1,-1);
	
	node (int ss,int ee){
		s = ss; e = ee; m = (s + e) / 2;
	}
	void create_all(){
		if (s != e){
			l = new node(s,m); r = new node(m+1,e);
			l->create_all(); r->create_all();
		}
	}
		
	void upd(pi line, node *prev){
		val = prev->val;
		
		if (s == e){
			if (f(line, s) < f(val, s)) val = line;
			return;
		}
		if (val == pi(-1,-1)){
			val = line; l = prev->l; r = prev->r;
		}else if (intersect(line, val) < m){
			if (f(line, m) < f(val, m)) swap(val, line);
			r = prev->r;
			l = new node(s,m);
			l->upd(line, prev->l);
		}else{
			if (f(line, m) < f(val, m)) swap(val, line);
			l = prev->l;
			r = new node(m+1,e);
			r->upd(line, prev->r);
		}
	}
	int qry(int x){
		if (s == e) return f(val, x);
		if (x > m) return min(f(val, x), r->qry(x));
		else return min(f(val, x), l->qry(x));
	}
	void del(){
		if (s != e){
			l->del(); r->del();
		}
		delete this;
	}
};
vector <node*> roots;
int suffmax[maxn];

int32_t main(){
    fast;
    
	cin >> N;
	FOR(i,1,N) cin >> T[i];
	DEC(i,N,1) suffmax[i] = max(suffmax[i+1], T[i]);
	stack <pi> st;
	node *root = new node(1,N);
	root->create_all();
	roots.pb(root);
	
	dp[N+1] = 0;
	DEC(i,N,1){
		//~ int mx = -1;
		//~ dp[i] = INF;
		//~ FOR(k,i,N) {
			//~ mx = max(mx, T[k]);
			//~ if (k == N || T[k+1] > mx) dp[i] = min(dp[i], dp[k+1] + mx * (N - i + 1));
		//~ }
		while (!st.empty() && st.top().f <= T[i]){
			st.pop();
			if (!st.empty()){
				roots.back()->del();
				roots.pop_back();
			}
		}
		
		if (!st.empty()){
			node *newroot = new node(1,N);
			newroot->upd(pi(T[i],dp[st.top().s]), roots.back());
			roots.pb(newroot);
		}
		st.push(pi(T[i], i));
		
		dp[i] = suffmax[i] * (N - i + 1);
		if (!roots.empty()) dp[i] = min(dp[i], roots.back()->qry(N-i+1));
	}
	//~ FOR(i,1,N) cout << dp[i] << ' ';
	//~ cout << '\n';
	cout << dp[1];
	
	
}

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