oj.uz

Submission #342845

# Submission time Handle Problem Language Result Execution time Memory
342845 2021-01-03T01:44:40 Z FlashGamezzz Sails (IOI07_sails) C++11
80 / 100
 47 ms 2688 KB 
#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 ans = 0, sum = 0, carry = 0;
	for (int i = 100005; i > 0; i--){
		mpos[i] += carry; long long su = min(ms-1, mpos[i]);
		carry = mpos[i] - su; ans += ((su-1)*su)/(2ll); sum += su;
	}
	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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1132 KB Output is correct
2 Correct 2 ms 1132 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1132 KB Output is correct
2 Correct 2 ms 1132 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1132 KB Output is correct
2 Correct 2 ms 1132 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1132 KB Output is correct
2 Correct 3 ms 1132 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1132 KB Output is correct
2 Correct 3 ms 1132 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1292 KB Output is correct
2 Correct 15 ms 1648 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1648 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 1772 KB Output isn't correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2536 KB Output is correct
2 Correct 30 ms 2172 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 2688 KB Output is correct
2 Correct 32 ms 1896 KB Output is correct

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 2280 KB Output isn't correct
2 Halted 0 ms 0 KB -