Submission #341944

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
341944	2020-12-31T17:01:30 Z	phathnv	Hokej (COCI17_hokej)	C++11	120 / 120	142 ms	6636 KB

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++){
        start[i] = a[ptr].ind;
        res += (ll) a[ptr].q * a[ptr].e;
        int curTime = a[ptr].e;
        int curPlayer = a[ptr].ind;
        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, {curPlayer, a[ptr].ind}});
            res += (ll) a[ptr].q * x;
            curTime += x;
            curPlayer = a[ptr].ind;
            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

120.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	512 KB	Output is correct
2	Correct	2 ms	364 KB	Output is correct
3	Correct	7 ms	640 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	4 ms	492 KB	Output is correct
6	Correct	2 ms	492 KB	Output is correct
7	Correct	3 ms	492 KB	Output is correct
8	Correct	29 ms	1772 KB	Output is correct
9	Correct	142 ms	6636 KB	Output is correct
10	Correct	141 ms	6508 KB	Output is correct