oj.uz

Submission #131515

# Submission time Handle Problem Language Result Execution time Memory
131515 2019-07-17T08:33:38 Z sebinkim Bodyguards (CEOI10_bodyguards) C++14
100 / 100
 160 ms 12144 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pll;

pll A[202020], B[202020];
ll n, m;

void die() { printf("0\n"); exit(0); }

int main()
{
	ll i, j, s1, s2;
	
	scanf("%lld", &n);
	
	for(i=1; i<=n; i++){
		scanf("%lld%lld", &A[i].first, &A[i].second);
    }
	
	sort(A + 1, A + n + 1);
	
	for(i=n; i>=1; i--){
		A[i].second += A[i + 1].second;
	}
	
	scanf("%lld", &m);
	
	for(i=1; i<=m; i++){
		scanf("%lld%lld", &B[i].first, &B[i].second);
	}
	
	sort(B + 1, B + m + 1);
	reverse(B + 1, B + m + 1);
	
	for(i=1; i<=m; i++){
		B[i].second += B[i - 1].first;
		swap(B[i].first, B[i].second);
	}
	
	for(i=1, j=1, s1=0, s2=0; i<=n; i++){
		for(; j<=m && B[j].first <= A[i].first; j++){
			s2 += (B[j].first - B[j - 1].first) * B[j].second;
			if(s1 + (B[j].first - A[i - 1].first) * A[i].second < s2) die();
		}
		s1 += (A[i].first - A[i - 1].first) * A[i].second;
		if(s1 < s2 + (A[i].first - B[j - 1].first) * B[j].second) die();
	}
	
	printf("1\n");
	
	return 0;
}

Compilation message

bodyguards.cpp: In function 'int main()':
bodyguards.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
bodyguards.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &A[i].first, &A[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bodyguards.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &m);
  ~~~~~^~~~~~~~~~~~
bodyguards.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &B[i].first, &B[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 256 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 424 KB Output is correct
14 Correct 2 ms 404 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 424 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 380 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 3 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 3 ms 376 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 252 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 312 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 372 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 3 ms 452 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 5 ms 504 KB Output is correct
7 Correct 5 ms 632 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 6 ms 504 KB Output is correct
10 Correct 6 ms 504 KB Output is correct
11 Correct 5 ms 508 KB Output is correct
12 Correct 5 ms 504 KB Output is correct
13 Correct 5 ms 504 KB Output is correct
14 Correct 6 ms 632 KB Output is correct
15 Correct 6 ms 504 KB Output is correct
16 Correct 6 ms 632 KB Output is correct
17 Correct 6 ms 504 KB Output is correct
18 Correct 5 ms 504 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1400 KB Output is correct
2 Correct 20 ms 1160 KB Output is correct
3 Correct 33 ms 1676 KB Output is correct
4 Correct 34 ms 1656 KB Output is correct
5 Correct 35 ms 1660 KB Output is correct
6 Correct 39 ms 1784 KB Output is correct
7 Correct 28 ms 1440 KB Output is correct
8 Correct 39 ms 1848 KB Output is correct
9 Correct 38 ms 1704 KB Output is correct
10 Correct 37 ms 1772 KB Output is correct
11 Correct 37 ms 1748 KB Output is correct
12 Correct 40 ms 1912 KB Output is correct
13 Correct 37 ms 1764 KB Output is correct
14 Correct 39 ms 1920 KB Output is correct
15 Correct 40 ms 1892 KB Output is correct
16 Correct 38 ms 1912 KB Output is correct
17 Correct 39 ms 1912 KB Output is correct
18 Correct 38 ms 1812 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 2780 KB Output is correct
2 Correct 50 ms 2368 KB Output is correct
3 Correct 71 ms 3060 KB Output is correct
4 Correct 12 ms 888 KB Output is correct
5 Correct 81 ms 3544 KB Output is correct
6 Correct 62 ms 2772 KB Output is correct
7 Correct 73 ms 3192 KB Output is correct
8 Correct 11 ms 760 KB Output is correct
9 Correct 80 ms 3556 KB Output is correct
10 Correct 74 ms 3192 KB Output is correct
11 Correct 75 ms 3188 KB Output is correct
12 Correct 74 ms 3176 KB Output is correct
13 Correct 80 ms 3456 KB Output is correct
14 Correct 76 ms 3452 KB Output is correct
15 Correct 77 ms 3488 KB Output is correct
16 Correct 77 ms 3496 KB Output is correct
17 Correct 77 ms 3476 KB Output is correct
18 Correct 77 ms 3488 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 4716 KB Output is correct
2 Correct 112 ms 4728 KB Output is correct
3 Correct 97 ms 4216 KB Output is correct
4 Correct 38 ms 1820 KB Output is correct
5 Correct 121 ms 5148 KB Output is correct
6 Correct 112 ms 8404 KB Output is correct
7 Correct 89 ms 6904 KB Output is correct
8 Correct 118 ms 9140 KB Output is correct
9 Correct 146 ms 11352 KB Output is correct
10 Correct 146 ms 11228 KB Output is correct
11 Correct 147 ms 11280 KB Output is correct
12 Correct 145 ms 11260 KB Output is correct
13 Correct 145 ms 11256 KB Output is correct
14 Correct 17 ms 1484 KB Output is correct
15 Correct 159 ms 12144 KB Output is correct
16 Correct 159 ms 12024 KB Output is correct
17 Correct 160 ms 12068 KB Output is correct
18 Correct 146 ms 11288 KB Output is correct