QOJ.ac
QOJ
| ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|
| #1522 | #884400 | #10011. Lottery | bulijiojiodibuliduo | bulijiojiodibuliduo | Success! | 2025-02-06 03:29:03 | 2025-02-06 03:29:04 |
詳細信息
Extra Test:
Wrong Answer
time: 955ms
memory: 62080kb
input:
201 1000000 1000000 100 1 101 1 102 1 103 1 104 1 105 1 106 1 107 1 108 1 109 1 110 1 111 1 112 1 113 1 114 1 115 1 116 1 117 1 118 1 119 1 120 1 121 1 122 1 123 1 124 1 125 1 126 1 127 1 128 1 129 1 130 1 131 1 132 1 133 1 134 1 135 1 136 1 137 1 138 1 139 1 140 1 141 1 142 1 143 1 144 1 145 1 146 ...
output:
778451993800 37313
result:
wrong answer 1st numbers differ - expected: '20000000', found: '778451993800'
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #884400 | #10011. Lottery | bulijiojiodibuliduo | WA | 946ms | 160000kb | C++17 | 1.3kb | 2025-02-06 03:27:25 | 2025-02-06 03:29:30 |
answer
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
int n;
ll s,r;
ll val[303];
ll dp[20004000];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>s>>r;
int bound=inf;
int mnA=300;
for(int i=1;i<=n;i++)
{
int a;
ll b;
cin>>a>>b;
mnA=min(mnA,a);
val[a]=max(val[a],b);
}
ll A=1ll*inf*inf,B=1;
for(int i=1;i<=20000000&&1ll*i*(301-mnA)<=1500000000ll;i++)
{
for(int j=mnA;j<=i&&j<=300;j++)
dp[i]=max(dp[i],dp[i-j]+val[j]);
if(dp[i])
{
ll A2=dp[i]*i+r*s;
ll B2=dp[i];
if((longer)(B2)*A>(longer)(B)*A2)
{
A=A2;
B=B2;
}
}
}
ll g=gcd(A,B);
cout<<A/g<<" "<<B/g<<'\n';
return 0;
}