Submission #146327

#	Time	Username	Problem	Language	Result	Execution time	Memory
146327		Luca_Girbovan	Hokej (COCI17_hokej)	C++11	120 / 120	518 ms	17160 KiB

hokej

#include <iostream>
#include <algorithm>

using namespace std;

struct player{long long val;long long res;long long pos;};
struct change{long long minn;long long enter;long long exit;};

player v[500010];
change c[1000001];

long long start[7], x;
long long n, m, st, ch, timp, ii, jj, last, sol;

int cmp1(const player &a, const player &b){
      if (a.val != b.val)
            return a.val > b.val;
      else
            return a.res > b.res;
}
int cmp2(const change &a, const change &b){
      return a.minn < b.minn;
}

int main(){

      cin>>m;
      cin>>n;

      for(int i=1; i<=n; i++){
            cin>>v[i].val;
            cin>>v[i].res;
            v[i].pos=i;
      }
      sort(v+1, v+n+1, cmp1);


      timp=6*m;
      ii  = 1;
      last=-1;

      for(int i=1; i<=n; i++){

            if(v[i].res == m){
                  if(timp >= m){
                        if(x == 6){
                              start[6]=start[5];
                              start[5]=start[4];
                              start[4]=start[3];
                              start[3]=start[2];
                              start[2]=start[1];
                              start[1]=v[i].pos;
                        }else{
                              x++;
                              start[x]=v[i].pos;
                        }


                        timp -= m;
                        sol += v[i].val * m;
                        if (timp == 0)
                              break;
                        else
                              continue;
                  }
            }

            if(ii == 1)
                  if(x == 6){
                        start[6]=start[5];
                        start[5]=start[4];
                        start[4]=start[3];
                        start[3]=start[2];
                        start[2]=start[1];
                        start[1]=v[i].pos;
                  }else{
                        x++;
                        start[x]=v[i].pos;
                  }
            else{
                  c[++ch].minn = ii;
                  c[ch].enter = v[i].pos;
                  c[ch].exit = last;
            }


            last=v[i].pos;


            if (timp <= v[i].res){

                  sol += timp * v[i].val;
                  break;

            }else{


                  if (ii + v[i].res <= m)
                        ii += v[i].res;
                  else if (ii + v[i].res == m+1) {
                              last =-1;
                              ii = 1;
                        }else{
                              if(x == 6){
                                    start[6]=start[5];
                                    start[5]=start[4];
                                    start[4]=start[3];
                                    start[3]=start[2];
                                    start[2]=start[1];
                                    start[1]=v[i].pos;
                              }else{
                                    x++;
                                    start[x]=v[i].pos;
                              }
                              ii = v[i].res - m + ii;
                        }

                  timp -= v[i].res;
                  sol += v[i].res * v[i].val;


            }
      }
      sort(start+1, start+6+1);
      sort(c+1, c + ch + 1, cmp2);


      cout<<sol<<"\n";

      for (int i=1; i<=6; i++) {
            cout<<start[i]<<" ";
      }

      cout<<"\n";

      cout<<ch;

      cout<<"\n";

      for (int i=1; i<=ch; i++)
            cout<<c[i].minn-1<<" "<<c[i].exit<<" "<<c[i].enter<<"\n";

      return 0;
}

• Subtask 1: 120 / 120