oj.uz

Submission #342445

# Submission time Handle Problem Language Result Execution time Memory
342445 2021-01-02T06:44:37 Z shrek12357 Sails (IOI07_sails) C++14
30 / 100
 1000 ms 4012 KB 
#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());
	int ans = 0;
	for (int i = 0; i < n; i++) {
		priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
		for (int j = 0; j < p[i].first; j++) {
			pq.push({ cnt[j], j });
		}
		for (int j = 0; j < p[i].second; j++) {
			ans += pq.top().first;
			cnt[pq.top().second]++;
			pq.pop();
		}
	}
	cout << ans << endl;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 1456 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1085 ms 1388 KB Time limit exceeded

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1078 ms 1896 KB Time limit exceeded

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1046 ms 4012 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1057 ms 3064 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1085 ms 3040 KB Time limit exceeded
2 Halted 0 ms 0 KB -