Submission #1360918

#	Time	Username	Problem	Language	Result	Execution time	Memory
1360918		Aviansh	Tycho (BOI23_tycho)	C++20	32 / 100	2095 ms	15936 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int b,p,d,n;
    cin >> b >> p >> d >> n;
    int dp[p];
    iota(dp,dp+p,0);
    int las = 0;
    while(n--){
        int a;
        cin >> a;
        ///merge las-a range into dp
        int len = a-las-1;
        int base = (len/p)*d;
        int tillpos = p-len%p;
        for(int i = 0;i<p;i++){
            dp[i]+=base;
            if(i>=tillpos){
                dp[i]+=d;
            }
        }
        for(int i = 1;i<p;i++){
            dp[i%p]=min(dp[i%p],dp[(i-1)%p]+1);
        }
        //shift
        int temp[p];
        int delta = (len+1)%p;
        for(int i = 0;i<p;i++){
            temp[(i+delta)%p]=dp[i];
        }
        for(int i = 0;i<p;i++){
            dp[i]=temp[i];
        }
        las=a;
    }

    int a=b;
    ///merge las-a range into dp
    int len = a-las-1;
    int base = (len/p)*d;
    int tillpos = p-len%p;
    for(int i = 0;i<p;i++){
        dp[i]+=base;
        if(i>=tillpos){
            dp[i]+=d;
        }
    }
    for(int i = 1;i<p;i++){
        dp[i%p]=min(dp[i%p],dp[(i-1)%p]+1);
    }
    //shift
    int temp[p];
    int delta = (len+1)%p;
    for(int i = 0;i<p;i++){
        temp[(i+delta)%p]=dp[i];
    }
    for(int i = 0;i<p;i++){
        dp[i]=temp[i];
    }
    las=a;
    int ans = *min_element(dp,dp+p);
    ans+=b;
    cout << ans;
    return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 8
• Subtask 3: 5 / 5
• Subtask 4: 7 / 7
• Subtask 5: 0 / 15
• Subtask 6: 20 / 20
• Subtask 7: 0 / 35
• Subtask 8: 0 / 10