Submission #747877

#	Time	Username	Problem	Language	Result	Execution time	Memory
747877		socho	Discharging (NOI20_discharging)	C++14	100 / 100	139 ms	25640 KiB

Discharging

#include <bits/stdc++.h>
using namespace std;
void fast() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
}
void ran() {
	srand(chrono::steady_clock::now().time_since_epoch().count());
}
long long get_rand() {
	long long a = rand();
	long long b = rand();
	return a * (RAND_MAX + 1ll) + b;
}
void usaco() {
	freopen("problem.in", "r", stdin); 
	freopen("problem.out", "w", stdout);
}
template<typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;
// #define endl '\n'
// #define double long double
#define int long long
// const int MOD = 1000 * 1000 * 1000 + 7;
// const int MOD = 998244353;

int n;
const int MXN = 1000005;
int t[MXN], dp[MXN];

struct Line {
	int a, b;
	Line(int m, int c) {
		a = m;
		b = c;
	}
	int value(int x) {
		return a * x + b;
	}
};

// descending hull


struct CHT {
	vector<Line> hull;
	
	void addLine(Line c) {
		while (hull.size() >= 2) {
			Line a = hull[hull.size()-2];
			Line b = hull.back();
			// if (xinter(a, b) >= xinter(b, c)) {
			__int128 l = (b.b - a.b);
			__int128 m = b.a - c.a;
			__int128 e = (c.b - b.b);
			__int128 f = a.a - b.a;
			if (l * m >= e * f) {
				hull.pop_back();
			}
			else {
				break;
			}
		}
		hull.push_back(c);
	}
	
	int query(int x) {
		
		int low = 0;
		int high = hull.size() - 1;
		
		while (low < high) {
			int mid = (low + high) / 2;
			int v1 = hull[mid].value(x);
			int v2 = hull[mid+1].value(x);
			if (v1 < v2) {
				high = mid;
			}
			else {
				low = mid + 1;
			}
		}
		return hull[low].value(x);
		
	}
	
} cht;

signed main() {

	ran(); fast();

	cin >> n;
	for (int i=1; i<=n; i++) {
		cin >> t[i];
		t[i] = max(t[i], t[i-1]);
	}

	for (int i=1; i<=n; i++) {
		dp[i] = t[i] * (i + (n - i));
		cht.addLine(Line(-i, dp[i-1]));
		if (i > 1) dp[i] = min(dp[i], t[i] * (n + 1) + cht.query(t[i]));
		
	}
	
	cout << dp[n] << endl;

}

Compilation message (stderr)

Discharging.cpp: In function 'void usaco()':
Discharging.cpp:15:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  freopen("problem.in", "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Discharging.cpp:16:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  freopen("problem.out", "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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