Submission #142479

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
142479	2019-08-09T07:41:27 Z	Linca_Robert	Hokej (COCI17_hokej)	C++14	120 / 120	556 ms	16696 KB

hokej

#include<bits/stdc++.h>
using namespace std;

int N, M, K, K_mx;
long long dsp[10], val[1000005];
long long ans = 0;
pair< pair<long long,long long>, long long > arr[1000005];
vector< pair<long long,long long> > player[8];
vector< pair< long long, pair<long long,long long> > > mvs;

bool cmp( pair< pair<long long,long long>, long long > A, pair< pair<long long,long long>, long long > B ){
    if( A.first.first == B.first.first )
        return A.first.second > B.first.second;
    return A.first.first > B.first.first;
}

int main(){

    cin >> M >> N;
    for( int i = 1; i <= N; i++ ){
        cin >> arr[i].first.first >> arr[i].first.second;
        val[i] = arr[i].first.first;
        arr[i].second = i;
    }

    sort( arr + 1, arr + N + 1, cmp );

    for( int i = 1; i <= 6; i++ )
        dsp[i] = M;

    K = 1; K_mx = 6;
    for( int i = 1; i <= N; i++ ){

        while( dsp[K] == 0 && K <= K_mx )
            K++;

        if( K > K_mx )
            break;

        if( player[K].empty() ){
            dsp[K] -= arr[i].first.second;
            player[K].push_back( { arr[i].first.second, arr[i].second } );
            continue;
        }

        if( arr[i].first.second <= dsp[K] ){
            dsp[K] -= arr[i].first.second;
            player[K].push_back( { arr[i].first.second, arr[i].second } );
        }else{

            if( arr[i].first.second == M ){
                if( K_mx == K ){
                    player[K].push_back( { dsp[K], arr[i].second } );
                    dsp[K] = 0;
                }else{
                    player[K_mx].push_back( { arr[i].first.second, arr[i].second } );
                    K_mx--;
                }
                if( K > K_mx )
                    break;
                continue;
            }

            int x = arr[i].first.second - dsp[K];
            player[K].push_back( { dsp[K], arr[i].second } );
            dsp[K] = 0;
            if( K + 1 <= K_mx ){
                K++;
                player[K].push_back( { x, arr[i].second } );
                dsp[K] -= x;
            }else{
                break;
            }
        }

    }

    for( int i = 1; i <= 6; i++ )
        dsp[i] = player[i][0].first;

    for( int i = 1; i <= 6; i++ ){
        for( int p = 0; p < player[i].size(); p++ ){
            ans += 1LL * player[i][p].first * val[ player[i][p].second ];
            if( p != 0 ){
                mvs.push_back( { dsp[i], {player[i][p - 1].second, player[i][p].second} } );
                dsp[i] += player[i][p].first;
            }
        }
    }

    sort( mvs.begin(), mvs.end() );

    cout << ans << "\n";
    for( int i = 1; i <= 6; i++ )
        cout << player[i][0].second << " ";
    cout << "\n" << mvs.size() << "\n";
    for( int i = 0; i < mvs.size(); i++ )
        cout << mvs[i].first << " " << mvs[i].second.first << " " << mvs[i].second.second << "\n";
    return 0;
}

Compilation message

hokej.cpp: In function 'int main()':
hokej.cpp:82:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for( int p = 0; p < player[i].size(); p++ ){
                         ~~^~~~~~~~~~~~~~~~~~
hokej.cpp:97:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for( int i = 0; i < mvs.size(); i++ )
                     ~~^~~~~~~~~~~~

Subtask #1

120.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	380 KB	Output is correct
2	Correct	8 ms	504 KB	Output is correct
3	Correct	30 ms	1144 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	12 ms	760 KB	Output is correct
6	Correct	6 ms	504 KB	Output is correct
7	Correct	10 ms	632 KB	Output is correct
8	Correct	99 ms	4036 KB	Output is correct
9	Correct	556 ms	16596 KB	Output is correct
10	Correct	556 ms	16696 KB	Output is correct