QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#285594 | #5259. Skills in Pills | light_ink_dots# | WA | 11ms | 112916kb | C++14 | 2.6kb | 2023-12-16 20:34:32 | 2023-12-16 20:34:32 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<algorithm>
// #include<c//assert>
#include<vector>
using namespace std;
#define int long long
int n,k,j;
int prek,prej;
int res[5][2000000];
pair<int,int> Answ(int p1,int p2){
prek=p1,prej=p2;
int ed=0;
int ans=0;
int fl=0;
if(p1==1&&p2==2) fl=0;
else if(p1==2&&p2==1) fl=1;
else fl=2;
for(int i=2;i<=n+2;i++){
// cerr<<"? "<<i<<" "<<prej<<" "<<prek<<" "<<endl;
if(i-prek==k&&i-prej==j){
ed=i;break;
}
if(i-prek==k) prek=i,ans++;
if(i-prej==j) prej=i,ans++;
res[fl][i-2]=ans;
}
//2->ed
return make_pair(ed-2,ans);
}
int dp[2000000][2];
// namespace S{
// int dp[200][120][120];
// int main(){
// memset(dp,63,sizeof(dp));
// dp[0][0][0]=0;
// for(int i=1;i<=n;i++){
// for(int a=0;a<j;a++){
// for(int b=0;b<k;b++){
// //not choose
// dp[i][a+1][b+1]=min(dp[i][a+1][b+1],dp[i-1][a][b]);
// dp[i][0][b+1]=min(dp[i][0][b+1],dp[i-1][a][b]+1);
// dp[i][a+1][0]=min(dp[i][a+1][0],dp[i-1][a][b]+1);
// }
// }
// }
// int mins=1e9;
// for(int a=0;a<j;a++){
// for(int b=0;b<k;b++) {
// mins=min(mins,dp[n][a][b]);
// // if(mins==15) cerr<<
// }
// }
// cerr<<"?? "<<mins<<endl;
// return mins;
// }
// }
int32_t main(){
cin>>k>>j>>n;
memset(res,63,sizeof(res));
int fir=1ll*k*j/__gcd(k,j);
if(k==j){
int ans=n/k*2;
cout<<ans<<endl;
if(n%k==k-1) ans++;
//assert(ans==S::main());
return 0;
}
cerr<<"?? "<<k*j/__gcd(k,j)<<endl;
if(1ll*k*j/__gcd(k,j)>n){
auto[a,b]=Answ(2,2);
//assert(a==-2);
//assert(b==S::main());
cout<<b<<'\n';return 0;
}
auto[L0,w0]=Answ(2,2);
// exit(0);
auto[L1,w1]=Answ(1,2);
auto[L2,w2]=Answ(2,1);
memset(dp,63,sizeof(dp));
cerr<<"?? "<<L0<<" "<<w0<<endl;
dp[L0][0]=dp[L0][1]=2+w0;
for(int i=fir;i<=n;i++){
dp[i+L1][0]=min(dp[i+L1][0],dp[i][0]+w1+2);
dp[i+L1][1]=min(dp[i+L1][1],dp[i][0]+w1+2);
dp[i+L2][0]=min(dp[i+L2][0],dp[i][0]+w2+2);
dp[i+L2][1]=min(dp[i+L2][1],dp[i][0]+w2+2);
// dp[i+L1][0]=min(dp[i+L1][0],dp[i][0]+w1);
}
int ans=1e9;
// cerr<<"?? "
for(int i=1;i<=n;i++){
ans=min(ans,dp[i][0]+res[0][n-i]);
ans=min(ans,dp[i][1]+res[1][n-i]);
}
cout<<ans<<" "<<L0<<endl;
//assert(ans==S::main());
}
//3 5 28
// /2 3 8
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 11ms
memory: 112916kb
input:
3 9 20
output:
8 9
result:
wrong answer 1st lines differ - expected: '8', found: '8 9'