QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#883864#10011. Lotterybulijiojiodibuliduo#WA 50ms4224kbC++171.5kb2025-02-05 19:29:192025-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:25]
  • Judged
  • Verdict: WA
  • Time: 50ms
  • Memory: 4224kb
  • [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'