#include <cstdio>
#include <algorithm>
#define DIMN 500010
using namespace std;
int cmp (pair <int , pair <int,int> > x , pair <int , pair <int,int> > y){
if (x.first != y.first)
return x.first > y.first;
return x.second.first < y.second.first;
}
struct idk{
int time,idx,col;
} changes[4*DIMN];
pair <int, pair <int,int> > v[DIMN],w[DIMN];
int last[7],elem,n,m;
int full[10];
int cmp2 (idk x, idk y){
if (x.time != y.time)
return x.time < y.time;
else return x.idx < y.idx;
}
long long solve (int x){ /// x sunt clar pline
int i,luat,sum,start;
long long score;
for (i=1;i<=n;i++)
w[i] = v[i];
luat = 0;
sum = 0;
score = 0;
start = 1;
elem = 0;
for (i=1;i<=x;i++){
score = score + (long long)m * w[full[i]].first;
elem++;
changes[elem].time = 0; /// dupa sum minute
changes[elem].idx = w[full[i]].second.second; /// pe asta il pui
changes[elem].col = i;
}
for (i=1 ; i<=n ; i++){
if (w[i].second.first == m){
if (luat >= x)
w[i].second.first--;
else {
luat++;
continue;
}
}
score = score + (long long)w[i].first * min ( w[i].second.first , m - sum);
if (sum + min ( w[i].second.first , m - sum) == m){
elem++;
changes[elem].time = sum; /// dupa sum minute
changes[elem].idx = w[i].second.second; /// pe asta il pui
changes[elem].col = start;
/// din w[i], in start pui doar m - sum
start++;
if (start == 6-x+1)
break;
w[i].second.first -= min ( w[i].second.first , m - sum);
sum = 0;
if (w[i].second.first)
i--;
}
else {
elem++;
changes[elem].time = sum; /// dupa sum minute
changes[elem].idx = w[i].second.second; /// pe asta il pui
changes[elem].col = start;
/// pe coloana start, ai jucatorul i fully
int ant = w[i].second.first;
w[i].second.first -= min ( w[i].second.first , m - sum);
sum = sum + min ( ant , m - sum);
}
if (start == 6-x+1)
break;
}
return score;
}
int main()
{
//freopen ("a.in" , "r" , stdin);
//freopen ("a.out" , "w" , stdout);
int i,poz;
long long score;
scanf ("%d%d",&m,&n);
for (i=1;i<=n;i++){
scanf ("%d%d",&v[i].first , &v[i].second.first);
v[i].second.second = i;
}
sort (v+1 , v + n + 1,cmp);
int y = 0;
for (i=1;i<=n;i++){
if (v[i].second.first == m)
full[++y] = i;
if (y==6)
break;
}
score = 0;
for (i=0;i<=6;i++){ /// daca i sunt full
long long aux = solve (i);
if (score < aux){
score = aux;
poz = i;
}
}
solve(poz);
printf ("%lld\n",score);
sort (changes+1 , changes + elem + 1, cmp2);
int ok = 0;
for (i=1;i<=elem;i++){
if (changes[i].time == 0){ /// jucator initial
printf ("%d ",changes[i].idx);
last[changes[i].col] = changes[i].idx;
ok++;
if (ok == 6){
printf ("\n%d\n",elem-6);
}
}
else {
printf ("%d %d %d\n",changes[i].time , last[changes[i].col] , changes[i].idx);
last[changes[i].col] = changes[i].idx;
}
}
return 0;
}
Compilation message
hokej.cpp: In function 'int main()':
hokej.cpp:85:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d",&m,&n);
~~~~~~^~~~~~~~~~~~~~
hokej.cpp:87:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d",&v[i].first , &v[i].second.first);
~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
hokej.cpp:106:10: warning: 'poz' may be used uninitialized in this function [-Wmaybe-uninitialized]
solve(poz);
~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
4 ms |
504 KB |
Output is correct |
| 3 |
Correct |
12 ms |
1144 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
6 ms |
640 KB |
Output is correct |
| 6 |
Correct |
3 ms |
504 KB |
Output is correct |
| 7 |
Incorrect |
6 ms |
636 KB |
Output isn't correct |
| 8 |
Failed |
45 ms |
3620 KB |
some player fainted |
| 9 |
Incorrect |
228 ms |
16880 KB |
Output isn't correct |
| 10 |
Failed |
225 ms |
17068 KB |
some player fainted |
