Submission #498766

#	Time	Username	Problem	Language	Result	Execution time	Memory
498766		jiahng	Discharging (NOI20_discharging)	C++14	100 / 100	141 ms	22596 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){
	return line.f * x + line.s;
}

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

struct Hull{ // Min, decreasing gradients, increasing queries
	deque <pi> dq;
	int query(int x){
		while (dq.size() > 1 && f(dq[0], x) > f(dq[1], x)) dq.pop_front();
		return f(dq[0], x);
	}
	void insert(pi line){
		while (dq.size() > 1 && intersect(line, dq.back()) <= intersect(line, dq[dq.size() - 2])) dq.pop_back();
		dq.pb(line);
	}
}hull;
pi ssmx[maxn];

int32_t main(){
    fast;
    
	cin >> N;
	FOR(i,1,N) cin >> T[i];
	int mx = 1;
	
	int co = 1;
	FOR(i,1,N){
		if (T[i] >= T[mx]) mx = i;
		while (co <= mx){
			hull.insert(pi(-co, dp[co-1]));
			co++;
		}
		if (i > 1) dp[i] = min(T[mx]*N, hull.query(T[mx]) + T[mx] * (N + 1));
		else dp[i] = T[1] * N;
		
		
		//~ cout << dp[i] << ' ';
	}
	cout << dp[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