Submission #955927

#	Time	Username	Problem	Language	Result	Execution time	Memory
955927		Dan4Life	Overtaking (IOI23_overtaking)	C++17	0 / 100	2 ms	484 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<array<int,2>> 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 cur : t) 
        S[0].insert({cur.first,cur.second});
    S[0].insert({Y,n});
    for(int i = 0; i < m-1; i++){
        S[i+1].clear();
        int dis = s[i+1]-s[i], mx = 0, mx2 = 0, mxu = -1, pre=-1;
        for(auto cur : S[i]){
            auto u = cur[0];
            auto ind = cur[1];
            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 cur : S[m-1])
        if(cur[1]==n) return cur[0];
    return -1;
}

Compilation message (stderr)

overtaking.cpp: In function 'll arrival_time(ll)':
overtaking.cpp:29:26: warning: narrowing conversion of 'cur.std::pair<long long int, int>::first' from 'long long int' to 'int' [-Wnarrowing]
   29 |         S[0].insert({cur.first,cur.second});
      |                      ~~~~^~~~~
overtaking.cpp:30:18: warning: narrowing conversion of 'Y' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   30 |     S[0].insert({Y,n});
      |                  ^
overtaking.cpp:33:49: warning: unused variable 'mxu' [-Wunused-variable]
   33 |         int dis = s[i+1]-s[i], mx = 0, mx2 = 0, mxu = -1, pre=-1;
      |                                                 ^~~

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