Submission #233377

#	Time	Username	Problem	Language	Result	Execution time	Memory
233377		NONAME	Segway (COI19_segway)	C++17	100 / 100	305 ms	1524 KiB

segway

#include <bits/stdc++.h>
#define sz(x) int(x.size())
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#define N 100500
#define oo ll(1e16)
#define ft first
#define sd second
#define mp make_pair
#define pb push_back
#define ppb pop_back
#define el '\n'
#define elf endl
#define base ll(1e9 + 7)
using namespace std;
typedef long long ll;
typedef long double ld;

int n, m, a[N][3], up[N], tim[N];
vector <pair <int, int> > cur, nxt;
bool mk[N];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    in("input.txt");

    cin >> n;
    for (int i = 0; i < n; i++)
    for (int j = 0; j < 3; j++)
        cin >> a[i][j];

    cin >> m;

    for (int i = 0; i < m; i++) {
        int ps;
        cin >> ps;
        mk[ps] = 1;
    }

    for (int i = 0; i < n; i++)
        cur.pb(mp(0, i));

    for (int position = 0; position < 300; position++) {
        nxt.clear();
        sort(cur.begin(), cur.end());

        int cnt = 0;
        int lst = -1;
        for (int i = 0; i < n; i++) {
            int dst = cur[i].ft;
            int nm = cur[i].sd;

            if (dst != lst)
                cnt = i;
            lst = dst;

            if (mk[position] && up[nm] == 0)
                up[nm] = cnt % 20;

            if (up[nm] != 0) up[nm]--, dst++;
                else dst += a[nm][position / 100];

            nxt.pb(mp(dst, nm));
        }

        cur = nxt;
    }

    for (int i = 0; i < n; i++)
        tim[cur[i].sd] = cur[i].ft;

    for (int i = 0; i < n; i++)
        cout << tim[i] << el;
}

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