Submission #238194

#	Time	Username	Problem	Language	Result	Execution time	Memory
238194		NONAME	Hokej (COCI17_hokej)	C++17	120 / 120	194 ms	16376 KiB

hokej

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define el '\n'
#define pb push_back
#define mp make_pair
#define ft first
#define sd second
using namespace std;

typedef long long ll;

const int N = 5e5 + 10;

ll n, m, ans, ps[N], a[N], b[N], ost[N], start[N];
vector <pair <ll, pair <int, int> > > res;

bool cmp0(int x, int y) { return a[x] > a[y]; }
bool cmp1(int x, int y) { return b[x] > b[y]; }

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

    cin >> m >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
        ost[i] = b[i];
        ps[i] = i;
    }

    sort(ps, ps + n, cmp0);

    int p = 0;

    for (int team = 0; team < 6; ++team) {
        int cur = 0;
        while (cur < m) {
            int o = min(m - cur, ost[ps[p]]);

            ost[ps[p]] -= o;
            ans += o * a[ps[p]];

            p += !ost[ps[p]];

            cur += o;
        }
    }

    if (p == n || b[ps[p]] == ost[ps[p]]) {}
        else {
            b[ps[p]] -= ost[ps[p]];
            p++;
        }

    sort(ps, ps + p, cmp1);

    p = 0;

    for (int team = 0; team < 6; ++team) {
        start[team] = ps[p] + 1;
        int cur = b[ps[p]], lst = ps[p++];

        while (cur < m) {
            int o = min(m - cur, b[ps[p]]);

            b[ps[p]] -= o;
            res.pb(mp(cur, mp(lst + 1, ps[p] + 1)));
            lst = ps[p];

            p += !b[ps[p]];

            cur += o;
        }
    }

    sort(all(res));

    cout << ans << el;
    for (int i = 0; i < 6; ++i)
        cout << start[i] << ' ';
    cout << el << sz(res) << el;
    for (int i = 0; i < sz(res); ++i)
        cout << res[i].ft << ' ' << res[i].sd.ft << ' ' << res[i].sd.sd << el;
}

• Subtask 1: 120 / 120