QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #285562 | #5259. Skills in Pills | light_ink_dots# | WA | 8ms | 112976kb | C++14 | 2.2kb | 2023-12-16 20:19:07 | 2023-12-16 20:19:08 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cassert>
#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;i++){
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[200][100][100];
int dp[2000000][2];
int32_t main(){
cin>>k>>j>>n;
// 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;
memset(res,63,sizeof(res));
int fir=1ll*k*j/__gcd(k,j);
if(1ll*k*j/__gcd(k,j)>n){
auto[a,b]=Answ(0,0);
assert(a==-2);
cout<<b<<'\n';return 0;
}
auto[L0,w0]=Answ(2,2);
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;
}
//3 5 28
// /2 3 8
详细
Test #1:
score: 100
Accepted
time: 8ms
memory: 112976kb
input:
3 9 20
output:
8
result:
ok single line: '8'
Test #2:
score: 0
Accepted
time: 4ms
memory: 112744kb
input:
8 2 12
output:
7
result:
ok single line: '7'
Test #3:
score: 0
Accepted
time: 4ms
memory: 112752kb
input:
2 5 15
output:
10
result:
ok single line: '10'
Test #4:
score: 0
Accepted
time: 0ms
memory: 81724kb
input:
10 8 13
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 8ms
memory: 112916kb
input:
6 6 19
output:
6
result:
ok single line: '6'
Test #6:
score: 0
Accepted
time: 8ms
memory: 81512kb
input:
2 3 5
output:
3
result:
ok single line: '3'
Test #7:
score: 0
Accepted
time: 8ms
memory: 112804kb
input:
4 2 8
output:
6
result:
ok single line: '6'
Test #8:
score: -100
Wrong Answer
time: 4ms
memory: 112696kb
input:
5 5 5
output:
1000000000
result:
wrong answer 1st lines differ - expected: '2', found: '1000000000'