QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#285594#5259. Skills in Pillslight_ink_dots#WA 11ms112916kbC++142.6kb2023-12-16 20:34:322023-12-16 20:34:32

Judging History

你现在查看的是最新测评结果

  • [2023-12-16 20:34:32]
  • 评测
  • 测评结果:WA
  • 用时:11ms
  • 内存:112916kb
  • [2023-12-16 20:34:32]
  • 提交

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

详细

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'