oj.uz

답안 #342446

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
342446 2021-01-02T06:45:42 Z shrek12357 Sails (IOI07_sails) C++14
30 / 100
 1000 ms 3108 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());
	ll 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 748 KB Output is correct
2 Correct 16 ms 748 KB Output is correct

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 423 ms 864 KB Output is correct
2 Execution timed out 1047 ms 2496 KB Time limit exceeded

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1091 ms 1212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1069 ms 1132 KB Time limit exceeded

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1055 ms 1384 KB Time limit exceeded

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1093 ms 3108 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1094 ms 1904 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1095 ms 1892 KB Time limit exceeded
2 Halted 0 ms 0 KB -