Submission #381038

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
381038	2021-03-24T10:05:16 Z	IldarKA	Hokej (COCI17_hokej)	C++14	120 / 120	342 ms	6636 KB

hokej

#include <bits/stdc++.h>

using namespace std;
int m, n, k[500001], l[500001], id[500001];
bool cmp(int a, int b){
    return k[a] > k[b];
}
vector < pair < int, pair < int, int > > > v3;
vector < int > v2;
int main(){
    cin >> m >> n;
    for(int i = 1; i <= n; i++){
        cin >> k[i] >> l[i];
        id[i] = i;
    }
    sort(id + 1, id + 1 + n, &cmp);
    vector < pair < int, int > > v;
    int kol = m * 6;
    long long ans = 0;
    for(int i = 1; i <= n; i++){
        if(l[id[i]] <= kol){
            v.push_back({l[id[i]], id[i]});
            ans += l[id[i]] * 1ll * k[id[i]];
            kol -= l[id[i]];
        }
        else if(kol > 0){
            v.push_back({kol, id[i]});
            ans += kol * 1ll * k[id[i]];
            kol = 0;
        }
    }
    sort(v.begin(), v.end());
    cout << ans << '\n';
    kol = m;
    int row = 1;
    int pos = (int)v.size() - 1;
    int last = -1;
    while(row < 7){
        if(kol >= v[pos].first){
            if(last == -1){
                kol -= v[pos].first;
                last = v[pos].second;
                v2.push_back(last);
            }
            else{
                v3.push_back({m - kol, {last, v[pos].second}});
                kol -= v[pos].first;
                last = v[pos].second;
            }
        }
        else{
            v3.push_back({m - kol, {last, v[pos].second}});
            kol = m + kol - v[pos].first;
            last = v[pos].second;
            v2.push_back(last);
            row++;
        }
        if(kol == 0){
            row++;
            kol = m;
            last = -1;
        }
        pos--;
    }
    for(int i = 0; i < v2.size(); i++){
        cout << v2[i] << " ";
    }
    cout << '\n';
    sort(v3.begin(), v3.end());
    cout << v3.size() << '\n';
    for(int i = 0; i < v3.size(); i++){
        cout << v3[i].first << " " << v3[i].second.first << " " << v3[i].second.second << '\n';
    }
}

Compilation message

hokej.cpp: In function 'int main()':
hokej.cpp:65:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i = 0; i < v2.size(); i++){
      |                    ~~^~~~~~~~~~~
hokej.cpp:71:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int i = 0; i < v3.size(); i++){
      |                    ~~^~~~~~~~~~~

Subtask #1

120.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	4 ms	364 KB	Output is correct
3	Correct	17 ms	620 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	7 ms	492 KB	Output is correct
6	Correct	3 ms	492 KB	Output is correct
7	Correct	6 ms	492 KB	Output is correct
8	Correct	61 ms	1900 KB	Output is correct
9	Correct	342 ms	6636 KB	Output is correct
10	Correct	339 ms	6636 KB	Output is correct