oj.uz

Submission #121352

# Submission time Handle Problem Language Result Execution time Memory
121352 2019-06-26T12:11:09 Z turbat Sails (IOI07_sails) C++14
80 / 100
 72 ms 2976 KB 
#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.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 640 KB Output is correct
2 Correct 18 ms 896 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1024 KB Output is correct

Subtask #8
0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 2560 KB Output is correct
2 Correct 51 ms 2676 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 2936 KB Output is correct
2 Correct 46 ms 2448 KB Output is correct

Subtask #11
0 / 10.0

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