oj.uz

Submission #130728

# Submission time Handle Problem Language Result Execution time Memory
130728 2019-07-16T04:17:14 Z 구재현(#3176) Bodyguards (CEOI10_bodyguards) C++14
100 / 100
 174 ms 16372 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
using lint = long long;
using pi = pair<lint, lint>;

int n, m;
pi r[MAXN], c[MAXN];

struct cht{
	vector<pi> v;
	long double crs(pi x, pi y){
		return (long double)(y.second - x.second) / (x.first - y.first);
	}
	void add(pi x){
		while(v.size() >= 2 && crs(v[v.size() - 2], v.back()) >= crs(v.back(), x)){
			v.pop_back();
		}
		v.push_back(x);
	}
	lint query(long double x){
		while(v.size() >= 2 && v[v.size() - 2].first * x + v[v.size() - 2].second < 
			v.back().first * x + v.back().second){
			v.pop_back();
		}
		auto ans = min(3e18L, v.back().first * x + v.back().second);
		return (lint)round(ans);
	}
}cht;

int main(){
	scanf("%d",&n);
	for(int i=1; i<=n; i++) scanf("%lld %lld",&r[i].first,&r[i].second);
	scanf("%d",&m);
	for(int i=1; i<=m; i++) scanf("%lld %lld",&c[i].first,&c[i].second);
	sort(r + 1, r + n + 1);
	sort(c + 1, c + m + 1);
	for(int i=1; i<=n; i++){
		r[i].first *= r[i].second;
		r[i].first += r[i-1].first;
	}
	for(int i=1; i<=m; i++){
		c[i].first *= c[i].second;
		c[i].first += c[i-1].first;
	}
	for(int i=n; i>=0; i--){
		r[i].second += r[i+1].second;
	}
	for(int i=m; i>=0; i--){
		c[i].second += c[i+1].second;
	}
	lint ret = 2e18;
	for(int i=0; i<=m; i++) cht.add(pi(c[i + 1].second, c[i].first));
	for(int i=0; i<=n; i++) ret = min(ret, cht.query(r[i + 1].second) + r[i].first);
	if(r[n].first != ret) puts("0");
	else puts("1");
}

Compilation message

bodyguards.cpp: In function 'int main()':
bodyguards.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
bodyguards.cpp:33:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=n; i++) scanf("%lld %lld",&r[i].first,&r[i].second);
                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bodyguards.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&m);
  ~~~~~^~~~~~~~~
bodyguards.cpp:35:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=m; i++) scanf("%lld %lld",&c[i].first,&c[i].second);
                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
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 508 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 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 256 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 348 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 252 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 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

Subtask #3
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 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 348 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 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 380 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 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 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 3 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 3 ms 504 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 376 KB Output is correct
3 Correct 4 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 376 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2020 KB Output is correct
2 Correct 21 ms 1528 KB Output is correct
3 Correct 36 ms 2800 KB Output is correct
4 Correct 35 ms 2224 KB Output is correct
5 Correct 37 ms 2800 KB Output is correct
6 Correct 42 ms 3188 KB Output is correct
7 Correct 29 ms 2088 KB Output is correct
8 Correct 42 ms 3056 KB Output is correct
9 Correct 40 ms 2932 KB Output is correct
10 Correct 40 ms 2940 KB Output is correct
11 Correct 40 ms 2928 KB Output is correct
12 Correct 43 ms 3056 KB Output is correct
13 Correct 40 ms 2928 KB Output is correct
14 Correct 41 ms 3056 KB Output is correct
15 Correct 43 ms 3184 KB Output is correct
16 Correct 42 ms 3056 KB Output is correct
17 Correct 43 ms 3056 KB Output is correct
18 Correct 42 ms 2900 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 4972 KB Output is correct
2 Correct 56 ms 3572 KB Output is correct
3 Correct 75 ms 5352 KB Output is correct
4 Correct 13 ms 1144 KB Output is correct
5 Correct 88 ms 5736 KB Output is correct
6 Correct 66 ms 4972 KB Output is correct
7 Correct 77 ms 5356 KB Output is correct
8 Correct 11 ms 1144 KB Output is correct
9 Correct 84 ms 5612 KB Output is correct
10 Correct 83 ms 5468 KB Output is correct
11 Correct 78 ms 5356 KB Output is correct
12 Correct 78 ms 5352 KB Output is correct
13 Correct 85 ms 5740 KB Output is correct
14 Correct 80 ms 5612 KB Output is correct
15 Correct 80 ms 5608 KB Output is correct
16 Correct 83 ms 5608 KB Output is correct
17 Correct 80 ms 5600 KB Output is correct
18 Correct 82 ms 5608 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 6976 KB Output is correct
2 Correct 127 ms 6892 KB Output is correct
3 Correct 105 ms 6304 KB Output is correct
4 Correct 39 ms 2420 KB Output is correct
5 Correct 130 ms 7272 KB Output is correct
6 Correct 110 ms 6720 KB Output is correct
7 Correct 93 ms 9292 KB Output is correct
8 Correct 126 ms 11372 KB Output is correct
9 Correct 154 ms 15564 KB Output is correct
10 Correct 155 ms 15684 KB Output is correct
11 Correct 157 ms 15624 KB Output is correct
12 Correct 155 ms 15460 KB Output is correct
13 Correct 158 ms 15524 KB Output is correct
14 Correct 17 ms 2036 KB Output is correct
15 Correct 169 ms 16356 KB Output is correct
16 Correct 174 ms 16356 KB Output is correct
17 Correct 171 ms 16372 KB Output is correct
18 Correct 155 ms 15716 KB Output is correct