Submission #1076971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076971		Trent	Overtaking (IOI23_overtaking)	C++17	39 / 100	3521 ms	24912 KiB

overtaking

#include "overtaking.h"
#include "bits/stdc++.h"
using namespace std;
#define forR(i, x) for(int i = 0; i < (x); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
struct bus {
    ll t; int w;
};

vvll t, e;
vi pos;
int X;

void sortByTime(vector<bus>& bs) {
    sort(all(bs), [](bus a, bus b){return a.t < b.t;});
}
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    t = vvll(M, vll(N)), e = vvll(M-1, vll(N));
    pos = S;
    vector<bus> bs;
    forR(i, N) {
        bs.push_back({T[i], W[i]});
    }
    forR(i, M-1) {
        sortByTime(bs);
        forR(j, N) t[i][j] = bs[j].t;
        forR(j, N) e[i][j] = bs[j].t + (ll) bs[j].w * (S[i+1] - S[i]);
        forR(j, N) cerr << '[' << bs[j].t << ' ' << bs[j].w << ' ' << e[i][j] << ']' << ' ';
        cerr << '\n';
        ll cm = 0;
        for(int j = 0; j < N; ){
            ll cur = bs[j].t;
            int k=j;
            for(; k < N && bs[k].t == cur; ++k);
            REP(l, j, k) bs[l].t = max(e[i][l], cm);
            REP(l, j, k) cm = max(cm, e[i][l]);
            j = k;
        }
    }
    forR(j, N) cerr << '[' << bs[j].t << ' ' << bs[j].w << ']' << ' ';
    cerr << '\n';
    forR(j, N) t[M-1][j] = bs[j].t;
    ::X = X;

    forR(i, M) {
        forR(j, N) cerr << t[i][j] << ' ';
        cerr << '\n';
    }
    cerr << '\n';
    forR(i, M-1) {
        forR(j, N) cerr << e[i][j] << ' ';
        cerr << '\n';
    }
}

long long arrival_time(long long Y)
{
    int M = (int) pos.size(), N = t[0].size();
    forR(i, M-1) {
        ll ce = Y + (ll) X * (pos[i+1] - pos[i]);
        forR(j, N) if(t[i][j] < Y) ce = max(ce, e[i][j]);
        Y = ce;
    }
    return Y;
}

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