QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#883875 | #10011. Lottery | bulijiojiodibuliduo# | WA | 58ms | 4224kb | C++17 | 1.5kb | 2025-02-05 19:35:23 | 2025-02-05 19:35:23 |
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:35:23]
- 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,1};
rep(i,0,M) {
//(i + a[op] * t) + s / (f[i] + b[op] * t)
int tt=int(max(sqrt(1.*s/op/b[op]) - 1.*f[i]/b[op],0.0));
for (ll t=max(tt-10,0);t<=tt+10;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);
//printf("%lld %lld %.6f %lld\n",p.a,p.b,1.*p.a/p.b,t-tt);
if (p<ans) ans=p;
}
//puts("");
}
printf("%lld %lld\n",ans.a,ans.b);
}
详细
Test #1:
score: 100
Accepted
time: 58ms
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: 48ms
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: 56ms
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'