Submission #844979

#	Time	Username	Problem	Language	Result	Execution time	Memory
844979		nonono	Overtaking (IOI23_overtaking)	C++17	65 / 100	3545 ms	25516 KiB

overtaking

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

const int mxN = 1000;

struct Data {
    long long prevT;
    long long currE;
    int id;
    
    bool operator < (const Data &x) {
        if(prevT != x.prevT) return prevT < x.prevT;
        return currE < x.currE;
    }
};

Data f[mxN][mxN];
int n, m;
long long x;
long long s[mxN];

void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S) {
    n = N; 
    m = M;
    x = X;
    
    for(int i = 0; i < M; i ++) s[i] = S[i];
    
    for(int i = 0; i < M; i ++) {
        if(i == 0) {
            for(int j = 0; j < N; j ++) f[i][j] = {0, T[j], j};
            
            continue ;
        }
    
        for(int j = 0; j < N; j ++) {
            f[i][j].prevT = f[i - 1][j].currE;
            f[i][j].currE = f[i - 1][j].currE + 1LL * W[f[i - 1][j].id] * (S[i] - S[i - 1]);
            f[i][j].id = f[i - 1][j].id;
        }
        
        sort(f[i], f[i] + N);
        
        for(int j = 1; j < N; j ++) {
            f[i][j].currE = max(f[i][j].currE, f[i][j - 1].currE);
        }
    }
}

long long arrival_time(long long Y) {
    for(int i = 1; i < m; i ++) {
        int low = 0, high = n - 1;
        while(low <= high) {
            int mid = (low + high) / 2;
            if(f[i][mid].prevT < Y) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        
        Y = Y + x * (s[i] - s[i - 1]);
        Y = max(Y, (low ? f[i][low - 1].currE : 0));
    }

    return Y;
}

/*int main() {

    cin.tie(0)->sync_with_stdio(0);
    
    init(6, 4, {20, 10, 40, 0}, {5, 20, 20, 30}, 10, 4, {0, 1, 3, 6});
    cout << arrival_time(50) << "\n";
    
    return 0;
}*/

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