Submission #956396

#	Time	Username	Problem	Language	Result	Execution time	Memory
956396		Dan4Life	Overtaking (IOI23_overtaking)	C++17	39 / 100	3527 ms	63056 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;

const int mxN = (int)1010;
multiset<pair<ll,int>> S[mxN];
int l, n, m, x;
vector<pair<ll,int>> t;
vi s, w;

void init(int L, int N, vll T, vi W, int X, int M, vi S)
{
    l = L, n = N, m = M, x = X; int i = 0;
    for(auto u : T) t.pb({u,i}),i++;
    for(auto u : S) s.pb(u);
    for(auto u : W) w.pb(u); 
    w.pb(x);
}

ll arrival_time(ll Y){
    S[0].clear();
    for(auto [u,i] : t) 
        S[0].insert({u,i});
    S[0].insert({Y,n});
    for(int i = 0; i < m-1; i++){
        S[i+1].clear();
        ll dis = s[i+1]-s[i], mx = 0, mx2 = 0, mxu = -1, pre=-1;
        for(auto [u,ind] : S[i]){
            auto speed = w[ind];
            if(u!=pre) mx = max(mx, mx2);
            pre = u;
            S[i+1].insert({max(u+dis*speed,mx),ind});
            mx2 = max(mx2, u+dis*speed);
        }
    }
    for(auto [u,i] : S[m-1])
        if(i==n) return u;
    return -1;
}

Compilation message (stderr)

overtaking.cpp: In function 'll arrival_time(ll)':
overtaking.cpp:33:48: warning: unused variable 'mxu' [-Wunused-variable]
   33 |         ll dis = s[i+1]-s[i], mx = 0, mx2 = 0, mxu = -1, pre=-1;
      |                                                ^~~

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