Submission #1248240

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248240		janson0109	Overtaking (IOI23_overtaking)	C++17	0 / 100	0 ms	328 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define lol ios::sync_with_stdio(false);cin.tie(NULL);
typedef long long ll;
typedef long double ld;
using namespace std;

vector<vector<ll>> pos ={{}}, dp, posx, posy;
ll k_,m_,x_;
vector<int> s_;

ll calc(ll k, ll M, vector<int> &s, ll p, ll X, ll h) {
    ll l = h - X * s[p];
    auto it = lower_bound(posx[p].begin(), posx[p].end(), h);
    if(it == posx[p].begin()) return ((s[M-1]-s[p])*X+h);
    ll y = (it-posx[p].begin())-1;
    auto it2 = lower_bound(posy[y].begin()+p+1, posy[y].end(), l);
    if(it2 == posy[y].end()) return ((s[M-1]-s[p])*X+h);
    ll z = it2-posy[y].begin();
    return dp[z][y];
}

void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> s)
{
    vector<pair<ll,ll>> bus;
    for(ll i=0; i<N; i++) bus.push_back(make_pair(W[i], T[i]));
    sort(bus.begin(), bus.end(), greater<pair<ll,ll>>());
    while(bus.back().F <= X) bus.pop_back();
    ll k = bus.size();
    for(ll i=0; i<k; i++) pos[0].push_back(bus[i].S);
    k_=k;m_=M;x_=X;s_=s;
    for(ll i=1; i<M; i++) {
        vector<pair<ll,ll>> cpos(k);
        for(ll j=0; j<k; j++) cpos[j] = make_pair(pos[i-1][j],j);
        sort(cpos.begin(), cpos.end());
        ll dist = s[i]-s[i-1];
        vector<ll> npos(k);
        for(ll j=0; j<k; j++) npos[j]=cpos[j].F + dist*bus[cpos[j].S].F;
        vector<ll> pre(k+1,0);
        for(ll j=0; j<k; j++) pre[j+1]=max(pre[j], npos[j]);
        ll l=0;
        for(ll j=0; j<k; j++) {
            if(j>0 && cpos[j].F != cpos[j-1].F) l=j;
            npos[j] = max(npos[j], pre[l]);
        }
        pos.push_back(vector<ll>(k));
        for(ll j=0; j<k; j++) pos[i][cpos[j].S] = npos[j];
    }
    posx = pos;
    for(ll i=0; i<M; i++) sort(posx[i].begin(), posx[i].end());
    for(ll i=0; i<k; i++) {
        posy.push_back({});
        for(ll j=0; j<M; j++) posy[i].push_back(posx[j][i] - X*s[j]);
    }
    for(ll i=0; i<M; i++) dp.push_back(vector<ll>(k));
    //for(ll i=M-1; i>=0; i--) {
    //    for(ll j=0; j<M; j++) dp[i][j] = calc(k, M, s, i, X, posx[i][j]);
    //}
    return; 
}

long long arrival_time(long long Y)
{
    return 0;
}

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