Submission #863038

#	Time	Username	Problem	Language	Result	Execution time	Memory
863038		faustaadp	Overtaking (IOI23_overtaking)	C++17	65 / 100	3508 ms	53328 KiB

overtaking

#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const ll NN = 2e5 + 5;
ll n, m, x;
ll a[NN], b[NN], jar[NN], sam[2020][2020];
vector<pair<ll, pll> > v[NN];
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    n = N;
    m = M;
    x = X;
    for(ll i = 0; i < n; i++)
    {
        a[i] = T[i];
        b[i] = W[i];
        // cout << a[i] << "dan" << b[i] << "ui\n";
    }
    for(ll i = 0; i < m; i++)
        jar[i] = S[i];
    for(ll i = 0; i < n; i++)
        sam[0][i] = a[i];
    for(ll i = 1; i < m; i++)
    {
        for(ll j = 0; j < n; j++)
        {
            v[i].pb(mp(sam[i - 1][j], mp(b[j], j)));
        }
        sort(v[i].begin(), v[i].end());
        ll lst = 0;
        for(auto z : v[i])
        {
            sam[i][z.se.se] = max(lst, sam[i - 1][z.se.se] + (jar[i] - jar[i - 1]) * z.se.fi);
            lst = sam[i][z.se.se];
        }
    }
    return;
}

long long arrival_time(long long Y)
{
    for(ll i = 1; i < m; i++)
    {
        pair<ll, pll> ban = mp(Y, mp(x, n));
        ll L = 0, R = v[i].size() - 1;
        ll lst = -1;
        while(L <= R)
        {
            ll C = (L + R) / 2;
            if(v[i][C] < ban)
            {
                lst = C;
                L = C + 1;
            }
            else
                R = C - 1;
        }
        if(lst >= 0)
            Y = max(sam[i][v[i][lst].se.se], Y + (jar[i] - jar[i - 1]) * ban.se.fi);
        else
            Y = Y + (jar[i] - jar[i - 1]) * ban.se.fi;
        // sort(v.begin(), v.end());
        // ll lst = 0;
        // for(auto z : v)
        // {
        //     // cout << "(" << i << "," << z.fi << ") " << sam[z.se.se] << " + " << (jar[i] - jar[i - 1]) << "*" << z.se.fi << "@\n";
        //     sam[z.se.se] = max(lst, sam[z.se.se] + (jar[i] - jar[i - 1]) * z.se.fi);
        //     lst = sam[z.se.se];
        // }
    }
    return Y;
}

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