Submission #1271176

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271176		mat_jur	Sails (IOI07_sails)	C++20	30 / 100	2 ms	1348 KiB

sails

#include "bits/stdc++.h"
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define cerr if(0)cout
#define debug(X) ;
#endif
using ll = long long;
#define all(v) (v).begin(), (v).end()
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back

const ll inf = ll(1e12);

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	
	int n;
	cin >> n;
	vector<int> a(n), b(n);
#ifndef DEBUG
	const int H = 1'003;
#else
	const int H = 10;
#endif

	vector<int> x(H);
	for (int i = 0; i < n; ++i) {
		cin >> a[i] >> b[i];
		for (int j = a[i] - 1; j >= a[i] - b[i]; --j) {
			x[j]++;
		}
	}
	
	debug(x);

	vector<ll> pref(H);
	pref[0] = x[0];
	for (int i = 1; i < H; ++i) pref[i] = x[i] + pref[i-1];

	for (int k = H-1; k >= 0; --k) {
		ll c = inf;
		for (int j = 0; j <= k; ++j) {
			ll s = ll(x[k]) + (k-1 < 0 ? 0 : pref[k-1]) - (j-1 < 0 ? 0 : pref[j-1]);
			c = min(c, s / (k - j + 1));
		}
		debug(k);
		debug(c);
		if (k) x[k-1] += x[k] - int(c);
		x[k] = int(c);
	}

	debug(x);

	ll res = 0;
	for (int k = 0; k < H; ++k)
		res += ll(x[k]) * (x[k] - 1) / 2;

	cout << res << '\n';
	
	return 0;
}

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