Submission #341943

#	Time	Username	Problem	Language	Result	Execution time	Memory
341943		phathnv	Hokej (COCI17_hokej)	C++11	72 / 120	146 ms	6508 KiB

hokej

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mxN = 500001;

struct data{
    int q, e, ind;
};

int m, n;
data a[mxN];

void ReadInput(){
    cin >> m >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i].q >> a[i].e;
        a[i].ind = i;
    }
}

void Solve(){
    sort(a + 1, a + 1 + n, [](const data &a, const data &b){
            if (a.q != b.q)
                return a.q > b.q;
            return a.e > b.e;
         });
    vector <int> start(6, 0);
    vector <pair<int, pair<int, int>>> answer;
    ll res = 0;
    int ptr = 1, lim = 5;
    for(int i = 0; i <= lim; i++){
        if (start[i])
            continue;
        start[i] = a[ptr].ind;
        res += (ll) a[ptr].q * a[ptr].e;
        int curTime = a[ptr].e;
        a[ptr].e = 0;
        ptr++;
        while (curTime < m){
            if (a[ptr].e == m && i < lim){
                start[lim] = a[ptr].ind;
                res += (ll) a[ptr].e * a[ptr].q;
                lim--;
                ptr++;
            }
            int x = min(m - curTime, a[ptr].e);
            answer.push_back({curTime, {a[ptr - 1].ind, a[ptr].ind}});
            res += (ll) a[ptr].q * x;
            curTime += x;
            a[ptr].e -= x;
            if (a[ptr].e == 0)
                ptr++;
        }
    }

    cout << res << '\n';
    for(int i = 0; i < 6; i++)
        cout << start[i] << ' ';
    cout << '\n';
    sort(answer.begin(), answer.end());
    cout << answer.size() << '\n';
    for(auto p : answer)
        cout << p.first << ' ' << p.second.first << ' ' << p.second.second << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ReadInput();
    Solve();
    return 0;
}

• Subtask 1: 72 / 120