This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <algorithm>
/*
2 3 2
0 2 5
1 1 3
*/
using namespace std;
#define INF 1<<29
#define MAXN 301
#define MAXM 301
typedef vector<int> vi;
typedef vector<vi> vvi;
int n,m,k,temp;
vvi x;
long getScore(vi tickets) {
int median = tickets.at(tickets.size() / 2);
int score = 0;
for(int num : tickets) {
score += abs(num - median);
}
return score;
}
long getBest(vvi x,int curRound, int curColor,vi curTickets,int curScore) {
if(curColor >= n) {
curScore += getScore(curTickets);
if(curRound >= (k - 1)) {
return curScore;
}
return getBest(x,curRound + 1,0,vi(),curScore);
}
int best = -1;
for(int i = 0; i < x.at(curColor).size(); ++i) {
int num = x[curColor][i];
int insertIndex = lower_bound(curTickets.begin(),curTickets.end(),num) - curTickets.begin();
curTickets.insert(curTickets.begin() + insertIndex,num);
x[curColor].erase(x.at(curColor).begin() + i);
int score = getBest(x,curRound,curColor + 1,curTickets,curScore);
if(score > best) {
best = score;
}
x.at(curColor).insert(x.at(curColor).begin() + insertIndex,num);
curTickets.erase(curTickets.begin() + insertIndex);
}
return best;
}
long find_maximum(int k, vvi x) {
::k = k;
n = x.size();
m = x.at(0).size();
return getBest(x,0,0,vi(),0);
}
/*
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m >> k;
for(int i = 0; i < n; ++i) {
x.push_back(vi());
for(int j = 0; j < m; ++j) {
cin >> temp;
x[i].push_back(temp);
}
}
cout << find_maximum(k,x);
return 0;
}
*/
Compilation message (stderr)
tickets.cpp: In function 'long int getBest(vvi, int, int, vi, int)':
tickets.cpp:46:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int i = 0; i < x.at(curColor).size(); ++i) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |