Submission #1182980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182980		amine_aroua	Long Distance Coach (JOI17_coach)	C++20	71 / 100	315 ms	327680 KiB

coach

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 3e18;
int calc_contrb(int mod , int t , int l , int r)
{
    if(l > r)
        return 0;
    // t | i - mod and i in [l , r]
    // t | i and i in [l - mod , r - mod]
    //    (l - mod)/t <=  k <= (r - mod) / t
    int lt = ceil(((double)(l - mod)) / t);
    int rt = floor(((double)(r - mod)) / t);
    return max(0ll , rt - lt + 1);
}
int fr_non_div(int t , int l , int r)
{
    if(l > r)
        return -1;
    // kt <= r
    int fr = (r / t) * t;
    return max(l , fr + 1);
}
int get_fr(int mod , int t, int l , int r)
{
    // k * t + mod >= l <-> k >= (l - mod)/t
    int k = ceil(((double)(l - mod)) / t);
    if(k * t + mod <= r)
        return k * t + mod;
    return INF;
}
int get_lst(int mod , int t , int l , int r)
{
    // k * t + mod <= r <-> k <= (r - mod) / t
    int k = floor(((double)(r - mod)) / t);
    if(k * t + mod >= l)
        return k * t + mod;
    return -1;
}
signed main()
{
    int x , n , m , w , t;
    cin>>x>>n>>m>>w>>t;
    vector<int> s(n + 2);
    s[n + 1] = x + 1;
    s[0] = -1;
    for(int i = 1 ; i <= n ; i++)
        cin>>s[i];
    n = (int)s.size();
    vector<pair<int ,int>> bros(m + 1);
    vector<int> d(m + 1);
    vector<int> c(m + 1);
    for(int i = 1 ; i <= m ; i++)
    {
        cin>>bros[i].first>>bros[i].second;
        d[i] = bros[i].first;
    }
    sort(s.begin() , s.end());
    sort(bros.begin() + 1, bros.end());
    for(int i = 1 ; i <= m ; i++)
    {
        c[i] = bros[i].second + c[i - 1];
    }
    sort(d.begin() + 1 , d.end());
    vector<vector<int>> cst(m + 1 , vector<int>(m + 1 , -1));
    int ans = 0;
    map<int ,int> occs;
    for(int i = n - 2 ; i >= 0 ; i--)
    {
        int l = s[i] + 1 , r = s[i + 1] - 1;
        int fr = fr_non_div(t ,l , r);
        int mn = s[i + 1];
        int mx = s[i];
        ans+=calc_contrb(0 , t , l , r) * w;
        for(int j = 1 ; j <=  m ;j++)
        {   
            ans+=(calc_contrb(bros[j].first, t ,l , r)) * w;
            if(fr != -1 && fr <= r)
            {
                mn = min(mn , get_fr(d[j] , t , fr,r));
                mx = max(mx , get_lst(bros[j].first , t , fr,r));
            }
        }
        // this range is [mn % t , mx % t]
        if(fr != -1 && fr <= r && mn != s[i + 1] && mx != s[i])
        {
            mn %= t;
            mx %= t;
            // cout<<mn % t<<'\n';
            // cout<<mx % t<<'\n';
            assert(binary_search(d.begin() , d.end() , mn));
            assert(binary_search(d.begin() , d.end() , mx));
            int lo = lower_bound(d.begin() + 1 , d.end() , mn) - d.begin();
            int hi = lower_bound(d.begin() + 1 , d.end() , mx) - d.begin();
            // cout<<l<<" "<<r<<" "<<mn<<" "<<mx<<" "<<lo<<" "<<hi<<'\n';
            int run = 0;
            for(int j = hi ; j >= lo ; j--)
            {
                run+=calc_contrb(d[j] , t , fr , x) - occs[d[j]];
                cst[j][hi] = max(cst[j][hi] , run * w);
            }
        }
        occs[s[i] % t]++;
    }
    // cout<<ans<<'\n';
    vector<int> dp(m + 1);
    for(int i = 1 ; i <= m ;  i++)
    {
        dp[i] = dp[i - 1];
        for(int j = 1 ; j <= i ; j++)
        {
            if(cst[j][i] != -1)
            {
                // cout<<"balalaw\n";
                // if(i == 2)
                // {
                //     cout<<j<<" "<<i<<'\n';
                //     cout<<cst[j][i]<<'\n';
                //     cout<<c[i] - c[j - 1] - cst[j][i]<<'\n';
                // }
                dp[i] = min(dp[i] , dp[j - 1] + c[i] - c[j - 1] - cst[j][i]);
            }       
        }
        // cout<<dp[i]<<'\n';
    }
    cout<<dp[m] + ans<<'\n';
    // map , go in backward to calc contribution
    
}

• Subtask 1: 16 / 16
• Subtask 2: 30 / 30
• Subtask 3: 25 / 25
• Subtask 4: 0 / 29