Submission #778986

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
778986	2023-07-11T06:10:49 Z	박상훈(#10000)	Bodyguards (CEOI10_bodyguards)	C++17	0 / 100	63 ms	5776 KB

bodyguards

#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	1 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	0 ms	212 KB	Output is correct
5	Incorrect	0 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	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Incorrect	212 KB	Output isn't correct
4	Halted	0 KB	-

Subtask #4
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 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	18 ms	1664 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	37 ms	3228 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	5580 KB	Output is correct
3	Correct	55 ms	5068 KB	Output is correct
4	Incorrect	28 ms	3108 KB	Output isn't correct
5	Halted	0 ms	0 KB	-