Submission #121352

#	Time	Username	Problem	Language	Result	Execution time	Memory
121352		turbat	Sails (IOI07_sails)	C++14	80 / 100	72 ms	2976 KiB

sails

#include <bits/stdc++.h>
using namespace std;
#define N 100005

int n, mh;
long long s, cnt[N], cnt1[N], ans, avr;
pair <int, int> mast[N];

int main (){
	cin >> n;
	for (int i = 0;i < n;i++){
		cin >> mast[i].first>> mast[i].second;
		s += mast[i].second;
		mh = max(mh, mast[i].first);
		cnt[mast[i].first]++;
		cnt[mast[i].first - mast[i].second]--;
	}
	for (int i = mh;i > 0;i--) cnt[i] += cnt[i + 1];
	for (int i = mh;i > 0;i--){
		avr = min(s / i, cnt[i]);
		cnt[i - 1] += cnt[i] - avr;
		cnt[i] = avr;
		s -= avr;
	}
	for (int i = 1;i <= mh;i++)
		ans += cnt[i] * (cnt[i] - 1) / 2;
	cout << ans << endl;
}

• 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