제출 #1360908

#제출 시각아이디문제언어결과실행 시간메모리
1360908AvianshTycho (BOI23_tycho)C++20
32 / 100
2095 ms15936 KiB
#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<2*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<2*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;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…