Submission #342447

#	Time	Username	Problem	Language	Result	Execution time	Memory
342447		shrek12357	Sails (IOI07_sails)	C++14	30 / 100	1093 ms	3316 KiB

sails

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <fstream>
#include <queue>
#include <stack>
#include <bitset>
//#include "molecules.h"
using namespace std;
#define ll long long
//cin.tie(0);ios_base::sync_with_stdio(0);

const int MAXN = 1e5 + 5;

vector<int> cnt(MAXN);

/*struct segtree {
	int size;
	vector<ll> tree;

	void init(int n) {
		size = 1;
		tree.assign(4 * n, 0LL);
		size = n;
	}

	void build(vector<ll>& a, int x, int lx, int rx) {
		if (rx == lx) {
			if (lx < a.size()) {
				tree[x] = lx;
			}
			return;
		}
		int m = (lx + rx) / 2;
		build(a, 2 * x, lx, m);
		build(a, 2 * x + 1, m + 1, rx);
		//tree[x] = min(cnt[tree[2 * x]], cnt[tree[2 * x + 1]]);
		if (cnt[tree[2 * x]] < cnt[tree[2 * x + 1]]) {
			tree[x] = 2 * x;
		}
		else {
			tree[x] = 2 * x + 1;
		}
	}

	void build(vector<ll>& a) {
		build(a, 1, 0, size - 1);
	}

	ll sum(int v, int tl, int tr, int l, int r) {
		if (l > r) {
			return 0;
		}
		if (l == tl && r == tr) {
			return tree[v];
		}
		int tm = (tl + tr) / 2;
		ll s1 = sum(v * 2, tl, tm, l, min(r, tm));
		ll s2 = sum(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
		//return s1 + s2;
		if (cnt[s1] < cnt[s2]) {
			return s1;
		}
		return s2;
	}

	ll sum(int l, int r) {
		return sum(1, 0, size - 1, l, r);
	}

	void update(int v, int tl, int tr, int pos, ll x) {
		if (tl == tr) {
			tree[v] = tl;
		}
		else {
			int tm = (tl + tr) / 2;
			if (pos <= tm) {
				update(v * 2, tl, tm, pos, x);
			}
			else {
				update(v * 2 + 1, tm + 1, tr, pos, x);
			}
			//tree[v] = tree[2 * v] + tree[2 * v + 1];
			if (cnt[tree[2 * v]] < cnt[tree[2 * v + 1]]) {
				tree[v] = tree[2 * v];
			}
			else {
				tree[v] = tree[2 * v + 1];
			}
		}
	}

	void update(int idx, ll val) {
		update(1, 0, size - 1, idx, val);
	}
};*/

int main() {
	int n;
	cin >> n;
	vector<pair<int, int>> p;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		p.push_back({ a, b });
	}
	sort(p.begin(), p.end());
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		vector<pair<int, int>> pq;
		for (int j = 0; j < p[i].first; j++) {
			pq.push_back({ cnt[j], j });
		}
		sort(pq.begin(), pq.end());
		for (int j = 0; j < p[i].second; j++) {
			ans += pq[j].first;
			cnt[pq[j].second]++;
		}
	}
	cout << ans << endl;
}

• 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