답안 #779181

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
779181	2023-07-11T08:44:44 Z	박영우(#10003)	Bodyguards (CEOI10_bodyguards)	C++17	100 / 100	125 ms	17264 KB

bodyguards

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 1010101
#define MAXS 22
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
#ifdef _MSC_VER
#  include <intrin.h>
#  define __builtin_popcount __popcnt
#endif
pll arr[MAX];
pll tr[MAX];
pll carr[MAX];
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int R, C;
	cin >> R;
	int i;
	for (i = 1; i <= R; i++) cin >> arr[i].first >> arr[i].second;
	sort(arr + 1, arr + R + 1);
	reverse(arr + 1, arr + R + 1);
	for (i = 1; i <= R; i++) tr[i] = pll(tr[i - 1].first + arr[i].second, arr[i].first - arr[i + 1].first);
	sort(tr + 1, tr + R + 1);
	reverse(tr + 1, tr + R + 1);
	int ptr = 0;
	for (i = 1; i <= R; i++) if (tr[i].second) arr[++ptr] = tr[i];
	R = ptr;
	cin >> C;
	for (i = 1; i <= C; i++) cin >> carr[i].first >> carr[i].second;
	sort(carr + 1, carr + C + 1);
	reverse(carr + 1, carr + C + 1);
	vector<ll> v;
	for (i = 1; i <= R; i++) arr[i].second += arr[i - 1].second, v.push_back(arr[i].second);
	for (i = 1; i <= C; i++) carr[i].second += carr[i - 1].second, v.push_back(carr[i].second);
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	ll pv = 0;
	int ptr1, ptr2;
	ptr1 = ptr2 = 1;
	arr[R + 1].second = carr[C + 1].second = 1e18;
	ll sum = 0;
	for (auto loc : v) {
		while (pv >= arr[ptr1].second) ptr1++;
		while (pv >= carr[ptr2].second) ptr2++;
		sum += (loc - pv) * arr[ptr1].first;
		sum -= (loc - pv) * carr[ptr2].first;
		pv = loc;
		if (sum < 0) {
			cout << 0 << ln;
			return 0;
		}
	}
	//assert(!sum);
	cout << 1 << ln;
}

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	0 ms	340 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	0 ms	340 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	468 KB	Output is correct

Subtask #6
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	0 ms	340 KB	Output is correct
18	Correct	0 ms	340 KB	Output is correct

Subtask #7
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	724 KB	Output is correct
2	Correct	2 ms	596 KB	Output is correct
3	Correct	2 ms	596 KB	Output is correct
4	Correct	2 ms	596 KB	Output is correct
5	Correct	2 ms	724 KB	Output is correct
6	Correct	3 ms	844 KB	Output is correct
7	Correct	3 ms	852 KB	Output is correct
8	Correct	2 ms	724 KB	Output is correct
9	Correct	3 ms	936 KB	Output is correct
10	Correct	3 ms	852 KB	Output is correct
11	Correct	3 ms	852 KB	Output is correct
12	Correct	3 ms	852 KB	Output is correct
13	Correct	3 ms	852 KB	Output is correct
14	Correct	3 ms	852 KB	Output is correct
15	Correct	3 ms	808 KB	Output is correct
16	Correct	3 ms	852 KB	Output is correct
17	Correct	3 ms	852 KB	Output is correct
18	Correct	3 ms	852 KB	Output is correct

Subtask #8
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	2540 KB	Output is correct
2	Correct	13 ms	2804 KB	Output is correct
3	Correct	25 ms	4436 KB	Output is correct
4	Correct	22 ms	4692 KB	Output is correct
5	Correct	23 ms	4748 KB	Output is correct
6	Correct	29 ms	5236 KB	Output is correct
7	Correct	18 ms	3468 KB	Output is correct
8	Correct	28 ms	5204 KB	Output is correct
9	Correct	24 ms	4940 KB	Output is correct
10	Correct	30 ms	4940 KB	Output is correct
11	Correct	24 ms	4936 KB	Output is correct
12	Correct	29 ms	5192 KB	Output is correct
13	Correct	24 ms	4920 KB	Output is correct
14	Correct	24 ms	5064 KB	Output is correct
15	Correct	24 ms	5072 KB	Output is correct
16	Correct	24 ms	5064 KB	Output is correct
17	Correct	26 ms	5064 KB	Output is correct
18	Correct	24 ms	4948 KB	Output is correct

Subtask #9
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	53 ms	6144 KB	Output is correct
2	Correct	35 ms	4428 KB	Output is correct
3	Correct	50 ms	6608 KB	Output is correct
4	Correct	7 ms	1364 KB	Output is correct
5	Correct	56 ms	7112 KB	Output is correct
6	Correct	44 ms	8076 KB	Output is correct
7	Correct	54 ms	9032 KB	Output is correct
8	Correct	7 ms	1620 KB	Output is correct
9	Correct	59 ms	9704 KB	Output is correct
10	Correct	50 ms	9100 KB	Output is correct
11	Correct	51 ms	9008 KB	Output is correct
12	Correct	48 ms	9048 KB	Output is correct
13	Correct	66 ms	9676 KB	Output is correct
14	Correct	48 ms	9544 KB	Output is correct
15	Correct	60 ms	9556 KB	Output is correct
16	Correct	48 ms	9544 KB	Output is correct
17	Correct	49 ms	9560 KB	Output is correct
18	Correct	48 ms	9536 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	78 ms	9384 KB	Output is correct
2	Correct	79 ms	9264 KB	Output is correct
3	Correct	65 ms	8216 KB	Output is correct
4	Correct	27 ms	3508 KB	Output is correct
5	Correct	87 ms	9908 KB	Output is correct
6	Correct	69 ms	15176 KB	Output is correct
7	Correct	60 ms	10468 KB	Output is correct
8	Correct	82 ms	14568 KB	Output is correct
9	Correct	107 ms	16160 KB	Output is correct
10	Correct	97 ms	16164 KB	Output is correct
11	Correct	109 ms	16096 KB	Output is correct
12	Correct	108 ms	16176 KB	Output is correct
13	Correct	97 ms	16136 KB	Output is correct
14	Correct	9 ms	2392 KB	Output is correct
15	Correct	117 ms	17264 KB	Output is correct
16	Correct	123 ms	17264 KB	Output is correct
17	Correct	125 ms	17228 KB	Output is correct
18	Correct	99 ms	16112 KB	Output is correct

답안 #779181

Compilation message