Submission #320027

#	Time	Username	Problem	Language	Result	Execution time	Memory
320027		gustason	Hokej (COCI17_hokej)	C++14	72 / 120	160 ms	20240 KiB

hokej

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Player {
    int quality, endurance, id;
    bool operator<(Player other) const {
        if (quality == other.quality)
            return endurance > other.endurance;
        return quality > other.quality;
    }
};
const int maxN = 500005;
vector<int> start6;
int mat[6][maxN];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int duration, n;
    cin >> duration >> n;
    Player p[n], p2[n];
    for(int i = 0; i < n; i++) {
        cin >> p[i].quality >> p[i].endurance;
        p[i].id = i+1;
        p2[i] = p[i];
    }

    sort(p, p+n);
    int starters = 0, leaveat = 0;
    ll Z = 0;
    for(int i = 0; i < n; i++) {
        if (starters == 5 && leaveat >= duration) break;
        if (mat[0][0] == 0) {
            start6.push_back(p[i].id);
            mat[0][0] = p[i].id;
            leaveat = p[i].endurance;
        } else if (leaveat + p[i].endurance > duration) {
            if (starters == 5) {
                mat[starters][leaveat] = p[i].id;
                Z += 1LL * (duration - leaveat) * p[i].quality;
                break;
            }
            if (leaveat < duration) {
                mat[starters][leaveat] = p[i].id;
                leaveat = p[i].endurance - (duration - leaveat);
            } else {
                leaveat = p[i].endurance;
            }
            starters++;
            mat[starters][0] = p[i].id;
            start6.push_back(p[i].id);
        } else {
            mat[starters][leaveat] = p[i].id;
            leaveat += p[i].endurance;
        }
        Z += 1LL * p[i].quality * p[i].endurance;
    }

    vector<array<int, 3>> subs;
    for(int i = 0; i < 6; i++) {
        int prev = mat[i][0];
        for(int j = 1; j <= duration; j++) {
            if (mat[i][j]) {
                array<int, 3> sub = {j, prev, mat[i][j]};
                subs.push_back(sub);
                prev = mat[i][j];
            }
        }
    }
    sort(subs.begin(), subs.end());

    cout << Z << "\n";
    for(auto i : start6) {
        cout << i << " ";
    }
    cout << "\n";
    cout << subs.size() << "\n";
    for(auto i : subs) {
        cout << i[0] << " " << i[1] << " " << i[2] << "\n";
    }

//    for(int i = 0; i < 6; i++) {
//        for(int j = 0; j <= duration; j++) {
//            cout << mat[i][j] << " ";
//        }
//        cout << "\n";
//    }
    return 0;
}
//~ check for overflows

• Subtask 1: 72 / 120