Submission #142472

#	Time	Username	Problem	Language	Result	Execution time	Memory
142472		Linca_Robert	Hokej (COCI17_hokej)	C++14	0 / 120	549 ms	8928 KiB

hokej

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

int N, M, K, K_mx, x[500005];
long long ans = 0;

struct player{
    int val, rez, id;
} arr[500005];

pair<int,int> team[8][500005];
int timp[8], pos[8];

int cnt = 0;
struct moves{
    int t, iese, intra;
} v[1000005];

inline bool cmp( player A, player B ){
    if( A.val == B.val )
        return A.rez > B.rez;
    return A.val > B.val;
}

inline bool cmp1( moves A, moves B ){
    return A.t < B.t;
}

int main(){

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

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

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

        while( K <= K_mx && timp[K] == M )
            K++;

        if( K > K_mx )
            break;

        if( arr[i].rez == M ){
            team[K_mx][ ++pos[K_mx] ].first = arr[i].id;
            team[K_mx][ pos[K_mx] ].second = arr[i].rez;
            timp[K_mx] = M;
            K_mx--;
            continue;
        }

        if( timp[K] + arr[i].rez <= M ){
            team[K][ ++pos[K] ].first = arr[i].id;
            team[K][ pos[K] ].second = arr[i].rez;
            timp[K] += arr[i].rez;
            continue;
        }else{
            team[K][ ++pos[K] ].first = arr[i].id;
            team[K][ pos[K] ].second = M - timp[K];
            K++;
            if( K > K_mx ){
                timp[K - 1] = M;
                break;
            }
            team[K][ ++pos[K] ].first = arr[i].id;
            team[K][ pos[K] ].second = arr[i].rez - M + timp[K - 1];
            timp[K - 1] = M;
            timp[K] = arr[i].rez - M + timp[K - 1];
        }
    }

    for( int i = 1; i <= 6; i++ ){
        timp[i] = team[i][1].second;
        ans += 1LL * team[i][1].second * x[ team[i][1].first ];
        for( int j = 2; j <= pos[i]; j++ ){
            ans += 1LL * team[i][j].second * x[ team[i][j].first ];
            v[++cnt] = { timp[i], team[i][j - 1].first, team[i][j].first };
            timp[i] += team[i][j].second;
        }
    }

    sort( v + 1, v + cnt + 1, cmp1 );

    cout << ans << "\n";
    for( int i = 1; i <= 6; i++ )
        cout << team[i][1].first << " ";
    cout << "\n" << cnt << "\n";
    for( int i = 1; i <= cnt; i++ )
        cout << v[i].t << " " << v[i].iese << " " << v[i].intra << "\n";
    return 0;
}

• Subtask 1: 0 / 120