#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
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){
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Execution timed out |
3082 ms |
460 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
Contestant returned 2260087452 but the tickets gives a total value of 2147483647 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Contestant returned 5 while correct return value is 6. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Contestant returned 11 while correct return value is 13. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Contestant returned 11 while correct return value is 13. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Contestant returned 11 while correct return value is 13. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Execution timed out |
3082 ms |
460 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
