#include "tickets.h"
#ifdef LOCAL
#include "grader.cpp"
#endif // LOCAL
#include <bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pb push_back
using namespace std;
const int N = 2e5 + 10;
int have[N];
ll cost(vector<int> a){
sort(a.begin(), a.end());
int n = a.size();
ll ans = 0;
for(int i = 0; i < n / 2; ++i)
ans += a[n / 2] - a[i];
for(int i = n / 2; i < n; ++i)
ans += a[i] - a[n / 2];
return ans;
}
ll find_maximum(int k, vector<vector<int>> x){
int n = x.size();
int m = x[0].size();
vector<pair<int, pair<int, int>>> a;
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
a.pb({x[i][j], {i, j}});
sort(a.begin(), a.end());
vector<vector<int>> ans;
ans.resize(n);
for(int i = 0; i < n; ++i){
ans[i].resize(m);
for(int j = 0; j < m; ++j)
ans[i][j] = -1;
}
int num = 0, l1 = 0, r1 = 0;
ll ans1 = 0;
vector<int> now;
int l = 0, r = a.size() - 1;
while(num < k){
while(l < r && have[a[l].s.f])
++l;
while(l < r && have[a[r].s.f])
--r;
if(a[l].s.f == a[r].s.f){
if(a[l].f - l1 < r1 - a[r].f)
--r;
else
++l;
continue;
}
ans[a[l].s.f][a[l].s.s] = num;
now.pb(a[l].f);
have[a[l].s.f] = 1;
ans[a[r].s.f][a[r].s.s] = num;
have[a[r].s.f] = 1;
now.pb(a[r].f);
if(now.size() == n){
ans1 += cost(now);
now.clear();
for(int i = 0; i < n; ++i)
have[i] = 0;
++num;
}
++l, --r;
}
allocate_tickets(ans);
return ans1;
}
/*
2 3 2
0 2 5
1 1 3
7
0 -1 1
-1 1 0
4 2 1
5 9
1 4
3 6
2 7
12
-1 0
0 -1
0 -1
-1 0
*/
Compilation message
tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:66:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
66 | if(now.size() == n){
| ~~~~~~~~~~~^~~~
# |
결과 |
실행 시간 |
메모리 |
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 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
2 ms |
716 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Incorrect |
1 ms |
204 KB |
Contestant returned 2516570860 while correct return value is 2727881086. |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
204 KB |
There is multiple tickets of color 1 on day 2 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
204 KB |
There is no ticket of color 0 on day 2 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
204 KB |
There is no ticket of color 0 on day 2 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
204 KB |
There is no ticket of color 0 on day 2 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
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 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
2 ms |
716 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Incorrect |
1 ms |
204 KB |
Contestant returned 2516570860 while correct return value is 2727881086. |
9 |
Halted |
0 ms |
0 KB |
- |