Submission #1218621

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218621		contorskii	Overtaking (IOI23_overtaking)	C++20	19 / 100	4 ms	4424 KiB

overtaking

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

const int mxN = 1e3+10;

int n, m, x;
vector<ll> t;
vector<int> s, w;
pair<ll, int> arr[mxN];
ll ans[mxN][mxN];

void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S) {
    n = 0; m = M; x = X; s = S;
    for(int i = 0; i < N; i++) {
        if(W[i] > x) {
            arr[n++] = {T[i], W[i]};
        }
    }
    if(n == 0) return ;
    sort(arr, arr+n);
    for(int i = 0; i < n; i++) {
        ans[0][i] = arr[i].first;
    }
    for(int j = 1; j < m; j++) {
        for(int i = 0; i < n; i++) {
            arr[i].first += 1LL * (s[j] - s[j-1]) * arr[i].second;
            if(i) arr[i].first = max(arr[i].first, arr[i-1].first);
        }
        sort(arr, arr+n);
        for(int i = 0; i < n; i++) {
            ans[j][i] = arr[i].first;
        }
    }
}

ll arrival_time(ll y) {
    int last_cnt = lower_bound(ans[0], ans[0]+n, y) - ans[0];
    --last_cnt;
    ll last = y;
    for(int j = 1; j < m; j++) {
        ll now = last + x * 1LL * (s[j] - s[j-1]);
        ll sc = 0;
        while(last_cnt >= 0 && ans[j][last_cnt] >= now) {
            sc = max(sc, ans[j][last_cnt]); --last_cnt;
        }
        now = max(sc, now); last = now;
        if(j == m-1) return now;
    }
}

Compilation message (stderr)

overtaking.cpp: In function 'll arrival_time(ll)':
overtaking.cpp:51:1: warning: control reaches end of non-void function [-Wreturn-type]
   51 | }
      | ^

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