oj.uz

Submission #778989

# Submission time Handle Problem Language Result Execution time Memory
778989 2023-07-11T06:12:41 Z 박상훈(#10000) Bodyguards (CEOI10_bodyguards) C++17
0 / 100
 63 ms 5776 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr ll INF = 4e18;
pair<ll, ll> a[200200], b[200200];
ll bS[200200];

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

struct Frac{
	ll a, b; // = a/b
	Frac(){}
	Frac(ll _a, ll _b): a(_a), b(_b) {}

	bool operator < (const Frac &F) const{
		return (__int128)a * F.b < (__int128)F.a * b;
	}
};

struct Line{
	ll a, b;
	Line(){}
	Line(ll _a, ll _b): a(_a), b(_b) {}

	ll operator () (ll x) const{
		return a*x + b;
	}
};

Frac cross(const Line &f, const Line &g){
	return Frac(g.b - f.b, f.a - g.a);
}

void solve(int n, int m){
	sort(a+1, a+n+1, greater<pair<ll, ll>>());
	sort(b+1, b+m+1, greater<pair<ll, ll>>());
	
	b[0].first = INF;
	bS[0] = 0;
	for (int i=1;i<=m;i++) bS[i] = bS[i-1] + b[i].second;

	int i = 1, j = m;
	ll c = 0, val = 0, sum = 0;

	while(i<n){
		ll nc = min(c + a[i].second, b[j].first);
		assert(c<=nc);

		if (c==nc){
			assert(nc < c + a[i].second);
			val += (ll)b[j].first * b[j].second;
			--j;
			continue;
		}

		Line f(a[i].first, sum - (ll)a[i].first * c);
		Line g(bS[j], val);

		if (f(c+1) > g(c+1)) NO();
		if (f.a > g.a && cross(f, g) < Frac(nc, 1)) NO();

		sum = f(nc);
		a[i].second -= nc-c;
		if (a[i].second==0) i++;
		if (b[j].first==nc){
			val += (ll)b[j].first * b[j].second;
			--j;
		}
		
	}

	printf("1\n");
}

int main(){
	int n, m;
	scanf("%d", &n);

	vector<int> X, Y;

	for (int i=1;i<=n;i++){
		ll x, y;
		scanf("%lld %lld", &x, &y);
		a[i] = {x, y};
		// for (int j=1;j<=y;j++) X.push_back(x);
	}

	scanf("%d", &m);
	for (int i=1;i<=m;i++){
		ll x, y;
		scanf("%lld %lld", &x, &y);
		b[i] = {x, y};
		// for (int j=1;j<=y;j++) Y.push_back(x);
	}

	solve(n, m);
	return 0;

	sort(X.begin(), X.end(), greater<int>());
	sort(Y.begin(), Y.end(), greater<int>());

	ll cur = 0;
	for (int i=0;i<(int)Y.size();i++){
		cur += Y[i];
		ll val = 0;
		for (int j=0;j<(int)X.size();j++) val += min(X[j], i+1);
		if (cur > val) NO();
	}


	printf("1\n");
}

Compilation message

bodyguards.cpp: In function 'int main()':
bodyguards.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
bodyguards.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |   scanf("%lld %lld", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~
bodyguards.cpp:92:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |  scanf("%d", &m);
      |  ~~~~~^~~~~~~~~~
bodyguards.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |   scanf("%lld %lld", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 5776 KB Output is correct
2 Correct 62 ms 5576 KB Output is correct
3 Correct 55 ms 5036 KB Output is correct
4 Incorrect 25 ms 2272 KB Output isn't correct
5 Halted 0 ms 0 KB -