Submission #262475

#	Time	Username	Problem	Language	Result	Execution time	Memory
262475		Cantfindme	Discharging (NOI20_discharging)	C++17	100 / 100	129 ms	22392 KiB

Discharging

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
const int maxn = 1000010;

#define ld long double
deque <pi> dq;
int n;
int T[maxn];
int jump[maxn];

int f(pi line, int x) {
	return line.f * x + line.s;
}

int query(int x) {
	while (dq.size() > 1) {
		if (f(dq[0],x) > f(dq[1],x)) dq.pop_front();
		else break;
	}
	return f(dq[0],x);
}

ld intersect(pi p1, pi p2) {
	return (ld) (p2.s - p1.s) / (p1.f - p2.f);
}

void insert(int m, int c) {
	pi line = pi(m,c);
	int s = dq.size();
	while (s > 1) {
		if (intersect(dq[s-1],line) <= intersect(dq[s-2],line)) dq.pop_back();
		else break;
		s = dq.size();
	}
	dq.push_back(line);
}

int32_t main() {
	FAST
	cin >> n;
	for (int i =1;i<=n;i++) cin >> T[i];
	
	pi curmax = pi(0,0);
	for (int i =1;i<=n;i++) {
		if (T[i] > curmax.f) {
			jump[i] = curmax.s;
			curmax = pi(T[i],i);
		}
	}
	
	int curx = curmax.s;
	insert(T[curx], 0);
	
	int bestprev = query(n - curx + 1);
	curx = jump[curx];
	
	while (curx != 0) {
		//cout << curx << " " << T[curx] << " " << bestprev << "\n";
		insert(T[curx], bestprev);
		bestprev = query((n - curx + 1));
		curx = jump[curx];
	}
	cout << bestprev;
	
}

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