QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#947730 | #10011. Lottery | hungry# | WA | 1ms | 4096kb | C++20 | 1.5kb | 2025-03-22 17:09:03 | 2025-03-22 17:09:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 i128;
typedef double db;
ll gcd(ll x, ll y){
if(!y) return x;
return gcd(y, x%y);
}
set<int> ch[310];
deque<int> ab[310];
int n;
ll r, s;
double suma, sumb;
double dlt(ll dx, ll dy){
return dx+1.00*r*s/(sumb+dy)-1.00*r*s/sumb;
}
void del(){
while(true){
int id = -1;
double now = 0;
for(int i = 1; i <= 300; i++){
if(ch[i].empty()) continue;
int dy = *ch[i].begin();
if(dlt(-i, -dy) < now) id = i, now = dlt(-i, -dy);
}
if(id == -1) break;
int dy = *ch[id].begin(); ch[id].erase(ch[id].begin());
suma -= id, sumb -= dy;
}
}
int main(){
scanf("%d%lld%lld", &n, &r, &s);
for(int i = 1; i <= n; i++){
int a, b; scanf("%d%d", &a, &b);
ab[a].push_back(b);
}
for(int i = 1; i <= 300; i++) sort(ab[i].begin(), ab[i].end(), greater<int> ());
int cnt = 0;
while(cnt < n){
for(int i = 1; i <= 300; i++){
if(ab[i].empty()) continue;
int y = ab[i][0]; ab[i].pop_front();
if(!cnt|| dlt(i, y) < 0){
suma += i, sumb += y;
ch[i].insert(y);
del();
}
cnt++;
}
}
ll A = suma*sumb+r*s, B = sumb;
ll g = gcd(A, B);
printf("%lld %lld\n", A/g, B/g);
return 0;
}
/*
3 11 3
1 3
2 7
5 13
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4096kb
input:
3 11 3 1 3 2 7 5 13
output:
63 10
result:
ok 2 number(s): "63 10"
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 4096kb
input:
8 608515 751563 113 451 9 4537 19 3343 79 855 260 4457 59 1650 142 3631 239 788
output:
457355493985 19712
result:
wrong answer 1st numbers differ - expected: '914765325642', found: '457355493985'