oj.uz

Submission #130723

# Submission time Handle Problem Language Result Execution time Memory
130723 2019-07-16T04:14:15 Z 구재현(#3176) Bodyguards (CEOI10_bodyguards) C++14
0 / 100
 123 ms 7020 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(lint 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();
		}
		return v[0].first * x + v[0].second;
	}
}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:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
bodyguards.cpp:32: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:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&m);
  ~~~~~^~~~~~~~~
bodyguards.cpp:34: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
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 Incorrect 2 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
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 Incorrect 2 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
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 Incorrect 2 ms 376 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 632 KB Output is correct
2 Incorrect 4 ms 504 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2036 KB Output is correct
2 Incorrect 21 ms 1500 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 4972 KB Output is correct
2 Incorrect 54 ms 3568 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

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