Submission #55553

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
55553	2018-07-08T00:34:00 Z	IvanC	Hokej (COCI17_hokej)	C++17	120 / 120	244 ms	18592 KB

hokej

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

typedef tuple<int,int,int> trinca;
typedef pair<int,int> ii;
typedef long long ll;

const int MAXN = 5*1e5 + 10;

vector<trinca> guloso,substituicoes;
vector<ii> greedy;
vector<int> escolhidos;
int qual[6][MAXN],N,M;
ll Z;

int main(){

	scanf("%d %d",&M,&N);
	for(int i = 1;i<=N;i++){
		int qualidade,dura;
		scanf("%d %d",&qualidade,&dura);
		guloso.push_back(make_tuple(qualidade,dura,i));
	}
	sort(guloso.begin(),guloso.end());

	int T_total = 6*M;

	while(T_total > 0){
		trinca davez = guloso.back();
		guloso.pop_back();
		int valor = get<0>(davez), tempo = get<1>(davez),identificacao = get<2>(davez);
		tempo = min(min(tempo,T_total),M);
		T_total -= tempo;
		Z += 1LL*valor*tempo;
		greedy.push_back(ii(tempo,identificacao));
	}
	guloso.clear();
	sort(greedy.begin(),greedy.end());

	for(int linha = 0;linha<6;linha++){
		for(int instante = 1;instante<=M;instante++){
			qual[linha][instante] = greedy.back().second;
			greedy.back().first--;
			if(greedy.back().first == 0) greedy.pop_back();
		}
	}
	for(int linha = 0;linha<6;linha++) escolhidos.push_back(qual[linha][1]);
	sort(escolhidos.begin(),escolhidos.end());
	for(int instante = 1;instante<M;instante++){
		for(int linha = 0;linha<6;linha++){
			if(qual[linha][instante] != qual[linha][instante+1]){
				substituicoes.push_back(make_tuple(instante,qual[linha][instante],qual[linha][instante+1]));
			}
		}
	}

	printf("%lld\n",Z);
	for(int i : escolhidos) printf("%d ",i);
	printf("\n");
	printf("%d\n",(int)substituicoes.size());
	for(trinca davez : substituicoes){
		printf("%d %d %d\n",get<0>(davez),get<1>(davez),get<2>(davez));
	}

	return 0;
}

Compilation message

hokej.cpp: In function 'int main()':
hokej.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&M,&N);
  ~~~~~^~~~~~~~~~~~~~~
hokej.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&qualidade,&dura);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

120.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	376 KB	Output is correct
2	Correct	6 ms	740 KB	Output is correct
3	Correct	31 ms	12564 KB	Output is correct
4	Correct	2 ms	12564 KB	Output is correct
5	Correct	14 ms	12564 KB	Output is correct
6	Correct	3 ms	12564 KB	Output is correct
7	Correct	5 ms	12564 KB	Output is correct
8	Correct	47 ms	12564 KB	Output is correct
9	Correct	244 ms	18544 KB	Output is correct
10	Correct	240 ms	18592 KB	Output is correct