Submission #421336

#	Time	Username	Problem	Language	Result	Execution time	Memory
421336		Apiram	Carnival Tickets (IOI20_tickets)	C++14	0 / 100	3082 ms	460 KiB

tickets

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

struct point{
int mi,mix,miy;
int ma,maxx,may;
};
int64_t  maxxy=0;
vector<pair<int,int>>opti;
void optimal(vector<point>arr,int j,vector<pair<int,pair<int,int>>>opt){
if (j>=arr.size()){
int64_t sum =INT_MAX;
for (int i =0;i<arr.size();++i){
int64_t counts=0;
for (int k =0;k<arr.size();++k){
  counts+=abs(opt[k].second.second - opt[i].second.second);
}
sum=min(counts,sum);
}
if (sum>maxxy){
maxxy=sum;
opti.clear();
for (int i =0;i<arr.size();++i){
opti.push_back({opt[i].first,opt[i].second.first});
}
}
return;
}
opt.push_back({arr[j].mix,{arr[j].miy,arr[j].mi}});
optimal (arr,j+1,opt);
opt.pop_back();
opt.push_back({arr[j].maxx,{arr[j].may,arr[j].ma}});
optimal(arr,j+1,opt);
opt.pop_back();
}

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	long long score=0;
	int m = x[0].size();
	vector<vector<int>>answer(n,vector<int>(m,-1));
	for (int it = 0;it<k;++it){
		vector<point>arr;
		for (int i =0;i<n;++i){
			point a;
	        	for (int j =0;j<m;++j){
	        	if (answer[i][j]==-1){
	        	 a.mi=x[i][j];
	        	 a.mix=i;
	        	 a.miy=j;
	        	 break;
	        	}
	        	}
	        	for (int j =m-1;j>=0;--j){
	        	if (answer[i][j]==-1){
	        	 a.ma=x[i][j];
	        	 a.maxx=i;
	        	 a.may=j;
	        	 break;
	        	}
	        	}
	        	arr.push_back(a);
		}

		vector<pair<int,pair<int,int>>>opt;
		maxxy=0;
		opti.clear();
		optimal(arr,0,opt);
		score+=maxxy;
		for (int i =0;i<n;++i){
		  answer[opti[i].first][opti[i].second]=it;
		}
	}
	allocate_tickets(answer);
	return score;
}

Compilation message (stderr)

tickets.cpp: In function 'void optimal(std::vector<point>, int, std::vector<std::pair<int, std::pair<int, int> > >)':
tickets.cpp:13:6: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 | if (j>=arr.size()){
      |     ~^~~~~~~~~~~~
tickets.cpp:15:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | for (int i =0;i<arr.size();++i){
      |               ~^~~~~~~~~~~
tickets.cpp:17:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 | for (int k =0;k<arr.size();++k){
      |               ~^~~~~~~~~~~
tickets.cpp:25:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 | for (int i =0;i<arr.size();++i){
      |               ~^~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10