제출 #1361161

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1361161		Aviansh	Tycho (BOI23_tycho)	C++20	13 / 100	11 ms	436 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int inf = LLONG_MAX;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int b,p,d,n;
    cin >> b >> p >> d >> n;
    int las = 0;
    map<int,int>mp;
    mp[0]=0;
    int delta = 0;
    int laz = 0;
    int sum = 0;
    auto join = [&] (int a){
        ///merge las to a range into dp
        int len = a-las-1;
        int base = (len/p)*d;
        int tillpos = p-len%p;
        ///add base to starting point delta.
        if(base){
            laz+=base;
        }
        ///now make range tillpos-p in this shifted version
        ///(tillpos+delta)%p -> delta
        tillpos-=delta;
        tillpos%=p;
        tillpos+=p;
        tillpos%=p;
        int tillneg = p-delta;
        tillneg%=p;
        tillneg+=p;
        tillneg%=p;
        if(tillneg==tillpos){
            //laz+=d;
        }
        else if(tillpos==0){
            //prefix
            laz+=d;
            if(tillneg){
                mp[tillneg]-=d;
                sum-=d;
            }
            else{
                laz-=d;
            }
        }
        else if(tillneg==0){
            //suffix
            auto it1 = mp.lower_bound(tillpos);
            if(it1==mp.end()){
                //do nothing
            }
            else{
                int fir = (*it1).first;
                int ol = (*it1).second;
                sum-=ol;
                ol+=d;
                mp.erase(it1);
                if(ol<0){
                    mp[fir]=ol;
                    sum+=ol;
                }
            }
        }
        else if(tillneg>tillpos){
            ///one single range
            auto it1 = mp.lower_bound(tillpos);
            auto it2 = mp.lower_bound(tillneg);
            if(it1==it2){
                //nothing happens
            }
            else{
                int add = d;
                if(tillneg){
                    mp[tillneg]-=d;
                    sum-=d;
                }
                else{
                    laz-=d;
                }
                contb:
                    it1 = mp.lower_bound(tillpos);
                    if(it1!=mp.end()){
                        int fir = (*it1).first;
                        int ol = (*it1).second;
                        sum-=ol;
                        ol+=add;
                        mp.erase(it1);
                        if(ol<0){
                            mp[fir]=ol;
                            sum+=ol;
                        }
                        else if(ol>0){
                            add=ol;
                            goto contb;
                        }
                    }
            }
        }
        else if(tillneg<tillpos){
            ///prefix and suffix
            ///MAY CAUSE BAD
            laz+=d;
            if(tillneg){
                mp[tillneg]-=d;
                sum-=d;
            }
            else{
                laz-=d;
            }
            auto it1 = mp.lower_bound(tillpos);
            if(it1==mp.end()){
                //do nothing
            }
            else{
                int add = d;
                conta:
                    it1 = mp.lower_bound(tillpos);
                    if(it1!=mp.end()){
                        int fir = (*it1).first;
                        int ol = (*it1).second;
                        sum-=ol;
                        ol+=add;
                        mp.erase(it1);
                        if(ol<0){
                            mp[fir]=ol;
                            sum+=ol;
                        }
                        else if(ol>0){
                            add=ol;
                            goto conta;
                        }
                    }
            }
        }
        else{
            //do nothing
        }
        if(p+sum<-1){
            ///end is lower than start.
            ///must reset
            ///assume mp[0]=0;
            int rval = p+sum;
            laz+=rval;
            rval=-rval;
            while(mp.size()&&rval){
                auto it = mp.begin();
                if(-(*it).second<=rval){
                    rval+=(*it).second;
                    sum-=(*it).second;
                    mp.erase(it);
                }
                else{
                    sum+=rval;
                    mp[(*it).first]+=rval;
                    rval=0;
                }
            }
            mp[0]=0;
        }
        //shift
        delta += (len+1)%p;
        delta%=p;
        las=a;
    };
    while(n--){
        int a;
        cin >> a;
        join(a);
    }
    join(b);
    int curr = laz;
    int ans = inf;
    las = 0;
    assert(mp[0]==0);
    for(pair<int,int>a:mp){
        curr+=a.second;
        curr+=(a.first-las);
        las=a.first;
        ans=min(ans,curr);
    }
    ans+=b;
    cout << ans;
    return 0;
}

• 서브태스크 1: 0 / 0
• 서브태스크 2: 8 / 8
• 서브태스크 3: 5 / 5
• 서브태스크 4: 0 / 7
• 서브태스크 5: 0 / 15
• 서브태스크 6: 0 / 20
• 서브태스크 7: 0 / 35
• 서브태스크 8: 0 / 10