Submission #1342349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1342349		Jakub_Wozniak	Tycho (BOI23_tycho)	C++20	47 / 100	2094 ms	9104 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll oo = (1e+18);
const int maxn = 1000009;
ll dpx[maxn];
ll Ts[maxn];
ll T[maxn];

ll Rt[maxn];
ll  S = 0;

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 <= p ; 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;
        for(int j = 0 ; j <= p ; j++)
        {
            Fie = 0;
            if(j >= S%p)
            {
                Fie = -d;
            }
            else
            {
                Fie = p;
            }
            dpx[i] = min(dpx[i] , Sg +  Rt[j]  + Fie);
        }
        Ts[i] = S;
        Rt[Ts[i]%p] = min(Rt[Ts[i]%p] , dpx[i] - (Ts[i]/p*d) - Ts[i] + Ts[i]%p);
    }

    cout << dpx[0] << '\n';
    return 0;
}

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