#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
typedef long long ll;
typedef long double ld;
const int INF = 1e9;
ll n, k, m;
vector<ll>mns, mxs, mns_, mxs_;
ll erkaranun[1507][1507];
ll cnt0[1507];
vector<pair<int, int>>d;
vector<int>os[1507], ls[1507];
int os_[1507], ls_[1507];
vector<vector<int>>ans;
vector<int>ap, am;
vector<vector<int>>a;
bool isap[1507];
bool isam[1507];
bool ismx[1507][1507];
bool ismn[1507][1507];
ll mxc[1507];
ll mnc[1507];
int mxi[1507], mni[1507];
ll dp[1507][1507];
ll DP[307][90007];
struct Ket {
int i, j, val;
Ket(int ii, int jj, int vl) {
i = ii;
j = jj;
val = vl;
}
bool operator<(const Ket& other)const {
return val < other.val;
}
friend ostream& operator<<(ostream& os, Ket val);
};
ostream& operator<<(ostream& os, Ket val) {
os << val.i << " " << val.j << ": " << val.val << "; ";
return os;
}
vector<vector<Ket>>s;
struct Tox{
int pr,sf,ogut,i;
Tox(int ii){
pr=k;
sf=0;
i=ii;
count_ogut();
for(int j=0;j<pr;j++){
ismn[i][s[i][j].j]=true;
}
}
void count_ogut(){
if(pr==0)ogut=-INF;
else ogut=s[i][m-sf-1].val+s[i][pr-1].val;
}
void update(){
ismn[i][s[i][pr-1].j]=false;
ismx[i][s[i][m-sf-1].j]=true;
pr--;
sf++;
count_ogut();
}
bool operator<(const Tox& other)const{
return ogut<other.ogut;
}
};
vector<Ket>sax;
priority_queue<Tox>q;
void give_max(int i, int r) {
////cout << "-- " << i << " " << r << " " << mxc[i] << endl;
mxc[i]--;
for (int j = mxi[i] + 1; j < m; j++) {
if (ismx[i][j]) {
////cout << j << endl;
mxi[i] = j;
ans[i][j] = r;
break;
}
}
}
void give_min(int i, int r) {
////cout << "== " << i << " " << r << endl;
mnc[i]--;
for (int j = mni[i] + 1; j < m; j++) {
if (ismn[i][j]) {
//////cout << j << " ";
mni[i] = j;
ans[i][j] = r;
break;
}
}
}
ll find_maximum(int K, vector<vector<int>> x) {
n = x.size();
m = x[0].size();
a=x;
k=K;
for (int i = 0; i < n; i++) {
vector<Ket>v;
s.push_back(v);
for (int j = 0; j < m; j++) {
Ket ket(i, j, x[i][j]);
s[i].push_back(ket);
}
sort(s[i].begin(), s[i].end());
Tox tox(i);
q.push(tox);
}
for(int i=0;i<n/2*k;i++){
Tox cur=q.top();
q.pop();
cur.update();
q.push(cur);
}
//4-i lucumy
ans.resize(n);
for (int i = 0; i < n; i++) {
ans[i].resize(m, -1);
}
mns.push_back(0);
mxs.push_back(0);
for (int i = 0; i < n; i++) {
mni[i] = -1;
mxi[i] = -1;
ll mn = INF, mx = 0;
int mn_ = -1, mx_ = -1;
for (int j = 0; j < m; j++) {
Ket ket(i, j, x[i][j]);
sax.push_back(ket);
if (x[i][j] < mn) {
mn_ = j;
}
if (x[i][j] > mx) {
mx_ = j;
}
mn = min(mn, x[i][j] * 1ll);
mx = max(mx, x[i][j] * 1ll);
}
mns.push_back(mn);
mxs.push_back(mx);
mns_.push_back(mn_);
mxs_.push_back(mx_);
}
sort(sax.begin(), sax.end());
ll res = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (ismn[i][j]) {
res -= x[i][j];
}
if (ismx[i][j]) {
res += x[i][j];
}
}
}
for (int i = 0; i < n; i++) {
bool is_ap = true;
bool is_am = true;
for (int j = 0; j < m; j++) {
if (ismx[i][j]) {
is_ap = false;
}
if (ismn[i][j]) {
is_am = false;
}
}
if (is_am) {
am.push_back(i);
isam[i] = true;
}
else if (is_ap) {
ap.push_back(i);
isap[i] = true;
}
else {
for (int j = 0; j < m; j++) {
if (ismx[i][j]) {
mxc[i]++;
}
if (ismn[i][j]) {
mnc[i]++;
}
}
}
}
////cout << "-> " << ap.size() << " " << am.size() << endl;
//////cout << ap[0] << endl;
for (int r = 0; r < k; r++) {
for (int tox : am) {
give_max(tox, r);
}
int cnt = 0;
for (int tox : ap) {
give_min(tox, r);
cnt++;
}
int len = m - r - 1;
for (int tox = 0; tox < n; tox++) {
if (!isap[tox] && !isam[tox]) {
if (cnt < n / 2) {
give_min(tox, r);
if (mnc[tox] == 0) {
isam[tox] = true;
am.push_back(tox);
}
cnt++;
}
else {
give_max(tox, r);
if (mxc[tox] == 0) {
isap[tox] = true;
ap.push_back(tox);
}
}
}
}
}
allocate_tickets(ans);
return res;
}
/*
3 1 1 1 2 3
4 4 4 1 1 1 0 1 0 0 1 0 0 0 1 1 1 0 1
7
4 4 4
5 8 6 9
4 1 5 2
3 6 5 7
8 4 5 9
29
5 5 5
1 2 3 6 5
4 8 5 2 7
9 4 5 8 9
5 6 4 8 4
2 5 1 4 6
69
5 5 4 1 2 3 6 5 4 8 5 2 7 9 4 5 8 9 5 6 4 8 4 2 5 1 4 6
4 4 4 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4
4 4 4 1 2 1 2 1 2 1 2 3 4 3 4 3 4 3 4
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
4 4 4 4 4 4 5 4 4 4 5 4 4 4 5 4 4 4 5
4 4 4 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
5
4 4 2
1 5 6 2
2 9 4 8
6 4 2 5
3 4 7 8
23
0 1 -1 -1
-1 0 -1 1
1 0 -1 -1
1 -1 -1 0
*/
Compilation message
tickets.cpp: In function 'll find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:213:13: warning: unused variable 'len' [-Wunused-variable]
213 | int len = m - r - 1;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
1364 KB |
Output is correct |
6 |
Correct |
4 ms |
5204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
3 ms |
1056 KB |
Output is correct |
5 |
Correct |
30 ms |
6608 KB |
Output is correct |
6 |
Correct |
732 ms |
123464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
392 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
2 ms |
1036 KB |
Output is correct |
5 |
Correct |
28 ms |
6576 KB |
Output is correct |
6 |
Correct |
607 ms |
124768 KB |
Output is correct |
7 |
Correct |
642 ms |
125240 KB |
Output is correct |
8 |
Correct |
3 ms |
1308 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
468 KB |
Output is correct |
12 |
Correct |
7 ms |
2192 KB |
Output is correct |
13 |
Correct |
21 ms |
6460 KB |
Output is correct |
14 |
Correct |
23 ms |
4764 KB |
Output is correct |
15 |
Correct |
650 ms |
125792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
3 ms |
1048 KB |
Output is correct |
5 |
Correct |
37 ms |
6720 KB |
Output is correct |
6 |
Correct |
6 ms |
1248 KB |
Output is correct |
7 |
Correct |
10 ms |
6212 KB |
Output is correct |
8 |
Correct |
977 ms |
126816 KB |
Output is correct |
9 |
Correct |
910 ms |
139244 KB |
Output is correct |
10 |
Correct |
877 ms |
138432 KB |
Output is correct |
11 |
Correct |
935 ms |
148548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
980 KB |
Output is correct |
3 |
Correct |
3 ms |
980 KB |
Output is correct |
4 |
Correct |
3 ms |
1108 KB |
Output is correct |
5 |
Correct |
3 ms |
1052 KB |
Output is correct |
6 |
Correct |
3 ms |
1108 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
656 KB |
Output is correct |
9 |
Correct |
3 ms |
1108 KB |
Output is correct |
10 |
Correct |
3 ms |
1108 KB |
Output is correct |
11 |
Correct |
3 ms |
1108 KB |
Output is correct |
12 |
Correct |
3 ms |
1108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
980 KB |
Output is correct |
3 |
Correct |
3 ms |
980 KB |
Output is correct |
4 |
Correct |
3 ms |
1108 KB |
Output is correct |
5 |
Correct |
3 ms |
1052 KB |
Output is correct |
6 |
Correct |
3 ms |
1108 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
656 KB |
Output is correct |
9 |
Correct |
3 ms |
1108 KB |
Output is correct |
10 |
Correct |
3 ms |
1108 KB |
Output is correct |
11 |
Correct |
3 ms |
1108 KB |
Output is correct |
12 |
Correct |
3 ms |
1108 KB |
Output is correct |
13 |
Correct |
29 ms |
6596 KB |
Output is correct |
14 |
Correct |
29 ms |
6664 KB |
Output is correct |
15 |
Correct |
33 ms |
6692 KB |
Output is correct |
16 |
Correct |
44 ms |
6656 KB |
Output is correct |
17 |
Correct |
2 ms |
596 KB |
Output is correct |
18 |
Correct |
3 ms |
1720 KB |
Output is correct |
19 |
Correct |
3 ms |
1548 KB |
Output is correct |
20 |
Correct |
27 ms |
6568 KB |
Output is correct |
21 |
Correct |
31 ms |
6444 KB |
Output is correct |
22 |
Correct |
28 ms |
6528 KB |
Output is correct |
23 |
Correct |
34 ms |
6516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
1364 KB |
Output is correct |
6 |
Correct |
4 ms |
5204 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
3 ms |
1056 KB |
Output is correct |
11 |
Correct |
30 ms |
6608 KB |
Output is correct |
12 |
Correct |
732 ms |
123464 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
392 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
2 ms |
1036 KB |
Output is correct |
17 |
Correct |
28 ms |
6576 KB |
Output is correct |
18 |
Correct |
607 ms |
124768 KB |
Output is correct |
19 |
Correct |
642 ms |
125240 KB |
Output is correct |
20 |
Correct |
3 ms |
1308 KB |
Output is correct |
21 |
Correct |
1 ms |
468 KB |
Output is correct |
22 |
Correct |
1 ms |
468 KB |
Output is correct |
23 |
Correct |
1 ms |
468 KB |
Output is correct |
24 |
Correct |
7 ms |
2192 KB |
Output is correct |
25 |
Correct |
21 ms |
6460 KB |
Output is correct |
26 |
Correct |
23 ms |
4764 KB |
Output is correct |
27 |
Correct |
650 ms |
125792 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
0 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
468 KB |
Output is correct |
31 |
Correct |
3 ms |
1048 KB |
Output is correct |
32 |
Correct |
37 ms |
6720 KB |
Output is correct |
33 |
Correct |
6 ms |
1248 KB |
Output is correct |
34 |
Correct |
10 ms |
6212 KB |
Output is correct |
35 |
Correct |
977 ms |
126816 KB |
Output is correct |
36 |
Correct |
910 ms |
139244 KB |
Output is correct |
37 |
Correct |
877 ms |
138432 KB |
Output is correct |
38 |
Correct |
935 ms |
148548 KB |
Output is correct |
39 |
Correct |
1 ms |
340 KB |
Output is correct |
40 |
Correct |
2 ms |
980 KB |
Output is correct |
41 |
Correct |
3 ms |
980 KB |
Output is correct |
42 |
Correct |
3 ms |
1108 KB |
Output is correct |
43 |
Correct |
3 ms |
1052 KB |
Output is correct |
44 |
Correct |
3 ms |
1108 KB |
Output is correct |
45 |
Correct |
1 ms |
468 KB |
Output is correct |
46 |
Correct |
1 ms |
656 KB |
Output is correct |
47 |
Correct |
3 ms |
1108 KB |
Output is correct |
48 |
Correct |
3 ms |
1108 KB |
Output is correct |
49 |
Correct |
3 ms |
1108 KB |
Output is correct |
50 |
Correct |
3 ms |
1108 KB |
Output is correct |
51 |
Correct |
29 ms |
6596 KB |
Output is correct |
52 |
Correct |
29 ms |
6664 KB |
Output is correct |
53 |
Correct |
33 ms |
6692 KB |
Output is correct |
54 |
Correct |
44 ms |
6656 KB |
Output is correct |
55 |
Correct |
2 ms |
596 KB |
Output is correct |
56 |
Correct |
3 ms |
1720 KB |
Output is correct |
57 |
Correct |
3 ms |
1548 KB |
Output is correct |
58 |
Correct |
27 ms |
6568 KB |
Output is correct |
59 |
Correct |
31 ms |
6444 KB |
Output is correct |
60 |
Correct |
28 ms |
6528 KB |
Output is correct |
61 |
Correct |
34 ms |
6516 KB |
Output is correct |
62 |
Correct |
85 ms |
17084 KB |
Output is correct |
63 |
Correct |
83 ms |
17008 KB |
Output is correct |
64 |
Correct |
94 ms |
17212 KB |
Output is correct |
65 |
Correct |
408 ms |
63928 KB |
Output is correct |
66 |
Correct |
431 ms |
64532 KB |
Output is correct |
67 |
Correct |
9 ms |
6212 KB |
Output is correct |
68 |
Correct |
6 ms |
1460 KB |
Output is correct |
69 |
Correct |
780 ms |
145576 KB |
Output is correct |
70 |
Correct |
881 ms |
146596 KB |
Output is correct |
71 |
Correct |
998 ms |
148492 KB |
Output is correct |
72 |
Correct |
742 ms |
130804 KB |
Output is correct |
73 |
Correct |
899 ms |
143420 KB |
Output is correct |
74 |
Correct |
687 ms |
129340 KB |
Output is correct |
75 |
Correct |
878 ms |
142008 KB |
Output is correct |