# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
142479 | Linca_Robert | Hokej (COCI17_hokej) | C++14 | 556 ms | 16696 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |