Submission #1342352

#TimeUsernameProblemLanguageResultExecution timeMemory
1342352Jakub_WozniakTycho (BOI23_tycho)C++20
90 / 100
53 ms18432 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll oo = (1e+18);
const int maxn = 1000009;
ll dpx[maxn];
ll T[maxn];
ll S = 0;

const ll base = (1<<20);
ll Rt[base*2];

void U(int X)
{
    X /= 2;
    while(X)
    {
        Rt[X] = min(Rt[2*X] , Rt[2*X+1]);
        X /= 2;
    }
}

ll Q(ll l , ll r)
{
    ll res = oo;
    l += base , r+= base;
    l--;
    r++;
    while(l/2 != r/2)
    {
        if((l&1) == 0)res = min(res,Rt[l+1]);
        if((r&1) == 1)res = min(res,Rt[r-1]);
        l /= 2;
        r /= 2;
    }
    return res;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n , b , d , p;
    cin >> b >> p >> d >> n;
    n++;
    T[0] = 0;
    T[n] = b;
    for(int i = 1; i < n ; i++)
    {
        cin >> T[i];
    }

    for(int j =0 ; j < 2*base ; j++)Rt[j] = oo;

    dpx[n] = oo;
    for(int i = n-1 ; i >= 0 ; i--)
    {
        ll A = T[i+1]-T[i];
        S += A;
        dpx[i] = S+S/p*d;
        if(S%p == 0)dpx[i] -= d;
        
        ll Fie = 0;
        ll Sg = S/p*d + S - S%p;

        if(S%p-1 >= 0)dpx[i] = min(dpx[i] , Sg + Q(0 + 1 , S%p-1 + 1) + p);
        dpx[i] = min(dpx[i] , Sg + Q(S%p + 1 , p + 1) - d);

        Rt[S%p + base + 1] = min(Rt[S%p + base + 1] , dpx[i] - (S/p*d) - S + S%p);
        U(S%p + base + 1);
    }

    cout << dpx[0] << '\n';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...