QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#883864 | #10011. Lottery | bulijiojiodibuliduo# | WA | 50ms | 4224kb | C++17 | 1.5kb | 2025-02-05 19:29:19 | 2025-02-05 19:29:25 |
Judging History
This is the latest submission verdict.
- [2025-02-06 03:29:21]
- hack成功,自动添加数据
- (/hack/1522)
- [2025-02-06 03:22:12]
- hack成功,自动添加数据
- (/hack/1521)
- [2025-02-06 03:14:39]
- hack成功,自动添加数据
- (/hack/1520)
- [2025-02-06 03:05:58]
- hack成功,自动添加数据
- (/hack/1519)
- [2025-02-06 03:02:43]
- hack成功,自动添加数据
- (/hack/1518)
- [2025-02-05 19:29:19]
- Submitted
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
const int M=100000;
int n,b[333];
int f[M+10];
ll s,r;
struct frac {
ll a,b;
};
bool operator < (frac a, frac b) {
return (__int128)a.a*b.b<(__int128)b.a*a.b;
}
int main() {
scanf("%d%lld%lld",&n,&s,&r);
s*=r;
rep(i,0,n) {
int a,c;
scanf("%d%d",&a,&c);
b[a]=max(b[a],c);
}
int op=-1;
rep(i,1,301) {
if (op==-1||b[i]*op>b[op]*i) op=i;
}
f[0]=0;
rep(i,0,M) rep(j,1,301) if (i>=j) {
f[i]=max(f[i],f[i-j]+b[j]);
}
frac ans{1ll<<60,0};
rep(i,0,M) {
//(i + a[op] * t) + s / (f[i] + b[op] * t)
int tt=int(max(sqrt(1.*s/op/b[op]) - f[i],0.0));
for (ll t=max(tt-10,0);t<=min(tt+10,0);t++) if (f[i]+b[op]*t>0) {
frac p{s,f[i]+b[op]*t};
p.a=p.a+(i+op*t)*(f[i]+b[op]*t);
if (p<ans) ans=p;
}
}
printf("%lld %lld\n",ans.a,ans.b);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 50ms
memory: 4224kb
input:
3 11 3 1 3 2 7 5 13
output:
63 10
result:
ok 2 number(s): "63 10"
Test #2:
score: 0
Accepted
time: 47ms
memory: 4224kb
input:
8 608515 751563 113 451 9 4537 19 3343 79 855 260 4457 59 1650 142 3631 239 788
output:
914765325642 15185339
result:
ok 2 number(s): "914765325642 15185339"
Test #3:
score: -100
Wrong Answer
time: 32ms
memory: 4224kb
input:
17 679894 524637 207 3634 275 1104 227 3130 226 1339 151 2999 121 2642 199 4470 112 4688 34 19 272 3032 84 2180 114 659 33 124 52 2086 212 546 199 497 198 311
output:
713197971134 3862912
result:
wrong answer 1st numbers differ - expected: '356598985567', found: '713197971134'