Submission #1146582

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146582		Tsagana	Sails (IOI07_sails)	C++20	100 / 100	54 ms	5188 KiB

sails

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

void solve () {
	int n;
	cin >> n;
	vector<pair<int, int>> a(n);
	for (auto &i: a) cin >> i.F >> i.S;
	sort(all(a));
	multiset<int> s;
	s.insert(0);
	for (auto i: a) {
		int h = i.F;
		int k = i.S;
		s.insert(h);
		auto p = s.ub(h - k), q = prev(p);
		int nxt = *q + *p - h + k;
		if (q != s.begin()) s.erase(q);
		s.insert(nxt);
		s.erase(p);
	}
	int ans = 0, cnt = 0;
	for (auto p = s.end(); p-- != s.begin(); cnt++) ans += cnt * *p;
	cout << ans;
}
signed main() {IOS solve(); return 0;}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10