Submission #1041450

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041450		vjudge1	Segway (COI19_segway)	C++17	100 / 100	58 ms	1052 KiB

segway

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

#define time first
#define dist second

const int N = 2e4 + 10, M = 325, A = 1.5e4 + 100;
int n, m, speed[N][3], a[M], nitro[N], pos[A];
pair<int, int> stat[N];

void reach(int i, int x){
    if (stat[i].dist >= x)
        return;

    int use = min(nitro[i], x - stat[i].dist);
    nitro[i] -= use;
    stat[i].time += use;
    stat[i].dist += use; 

    if (stat[i].dist < 100 and 100 <= x){
        stat[i].time += speed[i][stat[i].dist / 100] * (100 - stat[i].dist);
        stat[i].dist = 100;
    }
    if (stat[i].dist < 200 and 200 <= x){
        stat[i].time += speed[i][stat[i].dist / 100] * (200 - stat[i].dist);
        stat[i].dist = 200;
    }
    if (stat[i].dist < 300 and 300 <= x){
        stat[i].time += speed[i][stat[i].dist / 100] * (300 - stat[i].dist);
        stat[i].dist = 300;
    }

    stat[i].time += speed[i][stat[i].dist / 100] * (x - stat[i].dist);
    stat[i].dist = x;
}

int main(){
    cin >> n;
    for (int i = 1; i <= n; i ++){
        for (int j = 0; j < 3; j ++)
            cin >> speed[i][j];
        stat[i] = {0, 0};
    }
    cin >> m;
    for (int i = 0; i < m; i ++)
        cin >> a[i];
    a[m] = 300;

    for (int acc = 0; acc <= m; acc ++){
        memset(pos, 0, sizeof pos);
        for (int p = 1; p <= n; p ++)
            reach(p, a[acc]), pos[stat[p].time]++;

        for (int i = 1; i < A; i ++)
            pos[i] += pos[i - 1];

        for (int i = 1; i <= n; i ++){
            if (nitro[i]) continue;
            nitro[i] = pos[stat[i].time - 1] % 20;
        }
    }

    for (int i = 1; i <= n; i ++)
        cout << stat[i].first << endl;
}

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 45 / 45