Submission #80285

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
80285	2018-10-19T18:59:58 Z	wjoao	Hokej (COCI17_hokej)	C++11	120 / 120	405 ms	13104 KB

hokej

#include<bits/stdc++.h>
#define int long long
#define pii pair<int, int>

using namespace std;

struct V{
  int k, e, id;
  V(int _a, int _b, int _c){k = _a; e = _b; id = _c; }
  bool operator<(V &v2){
    return k > v2.k;
  }
};

struct OP{
  int tempo, id1, id2;
  OP(int _t, int _id1, int _id2){tempo = _t; id1 = _id1; id2 = _id2; }
  bool operator<( OP &op2){
    return tempo < op2.tempo;
  }
};

vector< V > v;
vector< pii > t;
vector< OP > r;
int n, m, k, e, ini[6];

main(){
  cin >> m >> n;

  for(int i = 1; i <= n; i++){
    cin >> k >> e;
    v.push_back(V(k,e, i));
  }

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

  int total = 0;
  int res_total = 0;
  for(int i = 0; i < v.size(); i++){
    if(total + v[i].e > m*6){
      res_total += v[i].k*(m*6-total);
      t.push_back(make_pair(m*6-total, v[i].id));
      break;
    }
    total += v[i].e;
    res_total += v[i].e*v[i].k;
    t.push_back(make_pair(v[i].e, v[i].id));
    if(total == m*6) break;
  }

  sort(t.begin(), t.end());
  reverse(t.begin(), t.end());

  ini[0] = t[0].second;
  int capacidade = t[0].first;
  int atual = 0;

  for(int i = 1; i < t.size(); i++){
    int last_id = t[i-1].second;
    if( capacidade == m ){
      atual++;
      capacidade = t[i].first;
      ini[atual] = t[i].second;
      //cout << "Começando o " << atual << " Com o : " << t[i].second << endl;
    } else if( capacidade + t[i].first <= m ){
      r.push_back(OP(capacidade, last_id, t[i].second));
      capacidade += t[i].first;
      //cout << "Adicionando o " << t[i].second << " No fim do atual: " << atual << " Com capacidade " << capacidade << endl;
    } else {
      r.push_back(OP(capacidade, last_id, t[i].second));
      capacidade = t[i].first - (m-capacidade);
      atual++;
      ini[atual] = t[i].second;

      //cout << "Adicionaodo o " << t[i].second << " No fim do atual: " << atual-1 << endl;
      // cout << "Começando o " << atual << " Com o : " << t[i].second << endl;
    }
  }


  sort(r.begin(), r.end());
  cout << res_total << endl;
  for(int i = 0; i < 6; i++){
    if( i > 0 ) cout << " ";
    cout << ini[i];
  }
  cout << endl << r.size() << endl;
  for(int i = 0; i < r.size(); i++){
    cout << r[i].tempo << " " << r[i].id1 << " " << r[i].id2 << endl;
  }

  return 0;
}

Compilation message

hokej.cpp:28:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
hokej.cpp: In function 'int main()':
hokej.cpp:40:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < v.size(); i++){
                  ~~^~~~~~~~~~
hokej.cpp:59:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < t.size(); i++){
                  ~~^~~~~~~~~~
hokej.cpp:89:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < r.size(); i++){
                  ~~^~~~~~~~~~

Subtask #1

120.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	6 ms	764 KB	Output is correct
3	Correct	23 ms	1324 KB	Output is correct
4	Correct	3 ms	1324 KB	Output is correct
5	Correct	10 ms	1324 KB	Output is correct
6	Correct	6 ms	1324 KB	Output is correct
7	Correct	8 ms	1324 KB	Output is correct
8	Correct	83 ms	3792 KB	Output is correct
9	Correct	400 ms	12972 KB	Output is correct
10	Correct	405 ms	13104 KB	Output is correct