#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
long long find_maximum(int k, std::vector<std::vector<int>> arr) {
ll n = arr.size();
ll m = arr[0].size();
std::vector<std::vector<int>> ans (n, vector < int > (m, -1));
ll sum = 0;
if (m == 1)
{
vector < pair < ll, ll > > mn (n), mx (n);
for (int i = 0; i < n; ++i)
{
mn[i] = { arr[i][0], i };
mx[i] = { arr[i][m - 1], i };
}
sort (mn.begin (), mn.end ());
sort (mx.begin (), mx.end ());
reverse (mx.begin (), mx.end ());
int i = 0, j = 0;
vector < bool > v (n);
for (int k = 0; k < n / 2; ++k)
{
while (v[mn[i].second]) ++i;
while (v[mx[j].second]) ++j;
if (mn[i].second != mx[j].second)
{
ans[mn[i].second][0] = 0;
ans[mx[j].second][m - 1] = 0;
sum += mx[j].first - mn[i].first;
v[mn[i].second] = v[mx[j].second] = true;
++i, ++j;
}
else if (j < n - 1 && mx[j + 1].first - mn[i].first > mx[j].first - mn[i + 1].first)
{
ans[mn[i].second][0] = 0;
ans[mx[j + 1].second][m - 1] = 0;
sum += mx[j + 1].first - mn[i].first;
v[mn[i].second] = v[mx[j + 1].second] = true;
++i, ++++j;
}
else
{
ans[mn[i + 1].second][0] = 0;
ans[mx[j].second][m - 1] = 0;
sum += mx[j].first - mn[i + 1].first;
v[mn[i + 1].second] = v[mx[j].second] = true;
++++i, ++j;
}
}
}
allocate_tickets(ans);
return sum;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
There is no ticket of color 0 on day 0 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
There is no ticket of color 0 on day 0 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
There is no ticket of color 0 on day 0 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
There is no ticket of color 0 on day 0 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
There is no ticket of color 0 on day 0 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Incorrect |
0 ms |
348 KB |
There is no ticket of color 0 on day 0 |
8 |
Halted |
0 ms |
0 KB |
- |