Submission #1246560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246560		walizamanee	Overtaking (IOI23_overtaking)	C++20	65 / 100	3596 ms	26180 KiB

overtaking

#include<bits/stdc++.h>
#include "overtaking.h"
using namespace std;

using ll = long long;
 vector<long long> tim;
 vector<long long> speed;
int n , m ;
 vector<pair<long long , long long>> dp[2001]; // ekhane hoitop swize thik koro
vector<long long> pref[2001];
long long goti;
vector<long long> terms;

void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S)
{   
   
    tim.clear();
    speed.clear();
    goti = (ll)X;
    terms.clear();

    for( int z = 0; z < M; z++ ) {
        terms.push_back((ll)S[z]);
    }

    for( int z = 0; z < N; z++ ) {
        if( W[z] > X ) {
            tim.push_back(T[z]);
            speed.push_back((ll)W[z]);
        }
    }
    n = tim.size();
    m = M;
   
    for( int z = 0; z <= m; z++ ) {
        dp[z].clear();
        pref[z].clear();
        dp[z].push_back({0 , 0});
        pref[z].push_back(0);
    }

    for( int z = 0; z < n; z++ ) {
        dp[0].push_back({tim[z] , speed[z]});
    }
    sort(dp[0].begin() , dp[0].end() );

    for( int z = 1; z < m; z++ ) {
        long long boro = 0;
        int here = 0;

        for( int y = 1; y <= n; y++ ) {

             ll uttor = ((ll)S[z] - (ll)S[z - 1]) * (dp[z - 1][y].second);
             uttor += dp[z - 1][y].first;

             if( dp[z - 1][y].first != dp[z - 1][y - 1].first ) {
                for( int x = here + 1; x < y; x++ ) {
                    boro = max( boro , dp[z][x].first );
                }
                here = y - 1;
             }
             uttor = max( uttor , boro );
             dp[z].push_back( { uttor , dp[z - 1][y].second } );
             pref[z - 1].push_back(uttor);
        }
        sort( dp[z].begin() , dp[z].end() );

    }
    
   // cerr << "done" << "\n";
     
}

long long arrival_time(long long Y)
{

    long long cur = Y;
    ll uttor = 0;
    for( int z = 0; z < m - 1; z++ ) {
        int l = 0;
        int r = n;
        while( l != r ) {
            int mid = (l + r + 1) / 2;
            if( dp[z][mid].first < cur ) {
                l = mid;
            }
            else r = mid - 1;
        }
        uttor = cur + ((terms[z + 1] - terms[z]) * goti);
        cur = max( uttor , pref[z][r] );
    }

    return cur;
}

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 26 / 26
• Subtask 5: 0 / 35