Submission #234444

#	Time	Username	Problem	Language	Result	Execution time	Memory
234444		VEGAnn	Hokej (COCI17_hokej)	C++14	120 / 120	180 ms	8568 KiB

hokej

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define a2 array<int,2>
#define a3 array<int,3>
#define PB push_back
using namespace std;
typedef long long ll;
const int N = 500100;
const int oo = 2e9;
vector<a3> evs;
int m, n, k[N], t[N], tt[N], nm[N], kol, start[10];
ll ans = 0;

bool cmp(int _x, int _y){
    return k[_x] > k[_y];
}

bool cmp1(int _x, int _y){
    return t[_x] > t[_y];
}

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

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> m >> n;

    for (int i = 0; i < n; i++) {
        cin >> k[i] >> t[i];
        tt[i] = t[i];
        nm[i] = i;
    }

    sort(nm, nm + n, cmp);

    int ptr = 0;

    for (int tp = 0; tp < 6; tp++){
        int tim = 0;

        while (tim < m){
            int i = nm[ptr];
            int cur = min(m - tim, tt[i]);

            tim += cur;
            tt[i] -= cur;
            ans += ll(cur) * ll(k[i]);

            if (tt[i] == 0)
                ptr++;
        }
    }

    if (ptr == n || tt[ptr] == t[ptr])
        kol = ptr;
    else {
        kol = ptr + 1;
        t[nm[ptr]] -= tt[nm[ptr]];
    }

    sort(nm, nm + kol, cmp1);

    int tp = 0;
    ptr = 0;

    while (tp < 6 && t[nm[ptr]] == m){
        start[tp] = nm[ptr];
        ptr++;
        tp++;
    }

    for (; tp < 6; tp++){
        int tim = 0;
        int lst = -1;

        while (tim < m){
            int i = nm[ptr];
            int cur = min(m - tim, t[i]);

            if (lst < 0)
                start[tp] = nm[ptr];
            else evs.PB({tim, lst, i});

            tim += cur;
            t[i] -= cur;

            lst = i;

            if (t[i] == 0)
                ptr++;
        }
    }

    sort(all(evs));

    cout << ans << '\n';

    for (int i = 0; i < 6; i++)
        cout << start[i] + 1 << " ";
    cout << '\n';

    cout << sz(evs) << '\n';

    for (a3 cr : evs)
        cout << cr[0] << " " << cr[1] + 1 << " " << cr[2] + 1 << '\n';

    return 0;
}

• Subtask 1: 120 / 120