Submission #1218620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218620		contorskii	Overtaking (IOI23_overtaking)	C++20	0 / 100	1 ms	840 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;
ll arr[mxN][mxN];
vector<ll> ans[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++][0] = T[i];
            w.push_back(W[i]);
            t.push_back(T[i]);
        }
    }
    vector<int> ord(n); iota(ord.begin(), ord.end(), 0);
    for(int i = 0; i < n; i++) ans[0].push_back(arr[i][0]);
    sort(ans[0].begin(), ans[0].end());
    for(int j = 1; j < m; j++) {
        sort(ord.begin(), ord.end(), [&](int x, int y) {
            if(arr[x][j-1] == arr[y][j-1]) return w[x] < w[y];
            return arr[x][j-1] < arr[y][j-1];
        });
        ll last = -1;
        for(int i = 0; i < n; i++) {
            int it = ord[i];
            arr[it][j] = arr[it][j-1] + w[it] * 1LL * (s[j] - s[j-1]);
            arr[it][j] = max(arr[it][j], last);
            last = max(last, arr[it][j]);
            ans[j].push_back(arr[it][j]);
        }
        sort(ans[j].begin(), ans[j].end());
    }
}

ll arrival_time(ll y) {
    int last_cnt = lower_bound(ans[0].begin(), ans[0].end(), y) - ans[0].begin();
    --last_cnt;
    ll last = y;
    for(int j = 1; j < m; j++) {
        ll now = last + x * (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:56:1: warning: control reaches end of non-void function [-Wreturn-type]
   56 | }
      | ^

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