Submission #342846

#	Time	Username	Problem	Language	Result	Execution time	Memory
342846		FlashGamezzz	Sails (IOI07_sails)	C++11	80 / 100	46 ms	2664 KiB

sails

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>

using namespace std;

int n; vector<pair<int, int> > msts;
long long ts = 0, mpos[100010];

bool check(long long ms){
	long long carry = 0;
	for (int i = 100005; i > 0; i--){
		if (mpos[i] > ms){
			carry += mpos[i]-ms;
		} else {
			carry = max((carry-ms+mpos[i]), 0ll);
		}
	}
	if (carry > 0ll){
		return false;
	}
	return true;
}
long long ga(long long ms){
	long long carry = 0, sum = 0, ans = 0, used = 0;
	for (int i = 100005; i > 0; i--){
		if (mpos[i] >= (ms-1)){
			used = ms-1;
		} else {
			if (carry+mpos[i] >= (ms-1)){
				used = ms-1;
			} else {
				used = carry+mpos[i];
			}
		}
		carry += mpos[i]-used; sum += used; ans += ((used)*(used-1))/2;
	}
	ans += (ts-sum) * (ms-1);
	return ans;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n;
	for (int i = 0; i < n; i++){
		int a, b; cin >> a >> b;
		msts.push_back(make_pair(a, b)); ts += b;
	}
	sort(msts.begin(), msts.end());
	for (int i = 0; i < n/2; i++){
		swap(msts[i], msts[n-i-1]);
	}
	int mstp = 0; priority_queue<int> pq;
	for (int i = 100005; i > 0; i--){
		while (mstp < n && i == msts[mstp].first){
			pq.push(i-msts[mstp].second); mstp++;
		}
		while (pq.size() > 0 && pq.top() == i){
			pq.pop();
		}
		mpos[i] = pq.size();
	}
	int low = 1, high = n+1;
	while (true){
		if (low == high){
			cout << ga(low) << endl; return 0;
		} else if (low + 1 == high){
			if (check(low)){
				cout << ga(low) << endl; return 0;
			}
			cout << ga(high) << endl; return 0;
		}
		int mid = (low+high)/2;
		if (check(mid)){
			high = mid;
		} else {
			low = mid;
		}
	}
}

• 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: 0 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 0 / 10