oj.uz

Submission #234444

# Submission time Handle Problem Language Result Execution time Memory
234444 2020-05-24T09:00:31 Z VEGAnn Hokej (COCI17_hokej) C++14
120 / 120
 180 ms 8568 KB 
#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.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 12 ms 768 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 7 ms 640 KB Output is correct
6 Correct 6 ms 512 KB Output is correct
7 Correct 7 ms 512 KB Output is correct
8 Correct 34 ms 2296 KB Output is correct
9 Correct 179 ms 8440 KB Output is correct
10 Correct 180 ms 8568 KB Output is correct