#ifdef EVAL
#include "tickets.h"
#endif
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#ifndef EVAL
vector<vector<int>> ans;
void allocate_tickets(vector<vector<int>> s) {
ans =s;
}
#endif
int k, n, m;
ll x[1505][1505];
int t[1505];
int L[1505], R[1505];
ll find_maximum(int kk, vector<vector<int>> xx) {
k = kk, n = (int)xx.size(),m = (int)xx[0].size();
for(int i=0;i<n;i++) {
for(int j= 0; j < m; j++)x[i][j] = xx[i][j];
}
ll S = 0;
for(int i =0;i<n;i++) t[i] = 0;
for(int i=0;i<n;i++){
for(int j=0;j<k;j++) S-=x[i][j];
}
priority_queue<pair<ll,int>, vector<pair<ll, int>>, less<pair<ll,int>>> Q;
for(int i= 0 ;i < n; i++) Q.push({x[i][m - 1]+x[i][k-1],i});
for(int i = 0; i < n/2*k; i++) {
int ind = Q.top().second;
Q.pop();
S+=x[ind][m-1-t[ind]]+x[ind][k-t[ind]-1];
t[ind]++;
if(t[ind]!=k)Q.push({x[ind][m-1-t[ind]]+x[ind][k-t[ind]-1],ind});
}
//return S;
for(int i =0; i < n;i++) {
//cout<<t[i]<< " ";
L[i] = R[i] = 0;
}
//return S;
vector<vector<int>> s(n, vector<int>(m, -1));
for(int z = 0; z < k; z++) {
vector<int> v, u, w;
for(int i = 0; i < n; i++) {
if(L[i] == k-t[i]) u.push_back(i); else if(R[i]==t[i]){ v.push_back(i); }else w.push_back(i);
}
assert((int)v.size()+(int)w.size()>=n/2);
assert((int)u.size()+(int)w.size()>=n/2);
int need = n/2 - (int)v.size();
for(int i : v) {
s[i][L[i]]=z;
L[i]++;
}
for(int i:u) {
s[i][m-R[i]-1]=z;
R[i]++;
}
for(int i=0; i<need;i++) {
s[w[i]][L[w[i]]]=z;
L[w[i]]++;
}
for(int i=need;i<(int)w.size();i++){
s[w[i]][m-R[w[i]]-1]=z;
R[w[i]]++;
}
}
allocate_tickets(s);
return S;
}
#ifndef EVAL
int main() {
freopen("D:/cp/oi/ioi/2020/input.txt", "r", stdin);
int nn, mm, kk;
cin>>nn>>mm>>kk;
vector<vector<int>> xx(nn, vector<int>(mm));
for(int i= 0; i < nn; i++){
for(int j = 0; j < mm;j++)cin>>xx[i][j];
}
cout<<find_maximum(kk,xx)<<endl;
//return 0;
//return 0;
for(int i = 0; i <nn; i++){
for(int j = 0; j <mm; j++) cout<<ans[i][j]<<" ";
cout<<endl;
}
return 0;
}
#endif
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
620 KB |
Output is correct |
5 |
Correct |
1 ms |
1644 KB |
Output is correct |
6 |
Correct |
5 ms |
6764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
3 ms |
876 KB |
Output is correct |
5 |
Correct |
29 ms |
5228 KB |
Output is correct |
6 |
Correct |
704 ms |
70948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
2 ms |
876 KB |
Output is correct |
5 |
Correct |
26 ms |
4588 KB |
Output is correct |
6 |
Correct |
651 ms |
74496 KB |
Output is correct |
7 |
Correct |
636 ms |
75040 KB |
Output is correct |
8 |
Correct |
6 ms |
1132 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
8 ms |
1644 KB |
Output is correct |
13 |
Correct |
23 ms |
4844 KB |
Output is correct |
14 |
Correct |
23 ms |
3436 KB |
Output is correct |
15 |
Correct |
659 ms |
75500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
3 ms |
876 KB |
Output is correct |
5 |
Correct |
34 ms |
5356 KB |
Output is correct |
6 |
Correct |
7 ms |
1004 KB |
Output is correct |
7 |
Correct |
13 ms |
7148 KB |
Output is correct |
8 |
Correct |
852 ms |
72684 KB |
Output is correct |
9 |
Correct |
812 ms |
68716 KB |
Output is correct |
10 |
Correct |
789 ms |
67636 KB |
Output is correct |
11 |
Correct |
851 ms |
72556 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
3 ms |
876 KB |
Output is correct |
3 |
Correct |
3 ms |
876 KB |
Output is correct |
4 |
Correct |
3 ms |
876 KB |
Output is correct |
5 |
Correct |
3 ms |
1004 KB |
Output is correct |
6 |
Correct |
3 ms |
876 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
748 KB |
Output is correct |
9 |
Correct |
3 ms |
876 KB |
Output is correct |
10 |
Correct |
3 ms |
876 KB |
Output is correct |
11 |
Correct |
3 ms |
876 KB |
Output is correct |
12 |
Correct |
3 ms |
876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
3 ms |
876 KB |
Output is correct |
3 |
Correct |
3 ms |
876 KB |
Output is correct |
4 |
Correct |
3 ms |
876 KB |
Output is correct |
5 |
Correct |
3 ms |
1004 KB |
Output is correct |
6 |
Correct |
3 ms |
876 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
748 KB |
Output is correct |
9 |
Correct |
3 ms |
876 KB |
Output is correct |
10 |
Correct |
3 ms |
876 KB |
Output is correct |
11 |
Correct |
3 ms |
876 KB |
Output is correct |
12 |
Correct |
3 ms |
876 KB |
Output is correct |
13 |
Correct |
35 ms |
5356 KB |
Output is correct |
14 |
Correct |
37 ms |
5228 KB |
Output is correct |
15 |
Correct |
33 ms |
5248 KB |
Output is correct |
16 |
Correct |
35 ms |
5304 KB |
Output is correct |
17 |
Correct |
1 ms |
492 KB |
Output is correct |
18 |
Correct |
3 ms |
1900 KB |
Output is correct |
19 |
Correct |
2 ms |
1644 KB |
Output is correct |
20 |
Correct |
29 ms |
4588 KB |
Output is correct |
21 |
Correct |
32 ms |
5100 KB |
Output is correct |
22 |
Correct |
30 ms |
4588 KB |
Output is correct |
23 |
Correct |
33 ms |
5100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
620 KB |
Output is correct |
5 |
Correct |
1 ms |
1644 KB |
Output is correct |
6 |
Correct |
5 ms |
6764 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
3 ms |
876 KB |
Output is correct |
11 |
Correct |
29 ms |
5228 KB |
Output is correct |
12 |
Correct |
704 ms |
70948 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
2 ms |
876 KB |
Output is correct |
17 |
Correct |
26 ms |
4588 KB |
Output is correct |
18 |
Correct |
651 ms |
74496 KB |
Output is correct |
19 |
Correct |
636 ms |
75040 KB |
Output is correct |
20 |
Correct |
6 ms |
1132 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
364 KB |
Output is correct |
24 |
Correct |
8 ms |
1644 KB |
Output is correct |
25 |
Correct |
23 ms |
4844 KB |
Output is correct |
26 |
Correct |
23 ms |
3436 KB |
Output is correct |
27 |
Correct |
659 ms |
75500 KB |
Output is correct |
28 |
Correct |
1 ms |
364 KB |
Output is correct |
29 |
Correct |
1 ms |
364 KB |
Output is correct |
30 |
Correct |
1 ms |
364 KB |
Output is correct |
31 |
Correct |
3 ms |
876 KB |
Output is correct |
32 |
Correct |
34 ms |
5356 KB |
Output is correct |
33 |
Correct |
7 ms |
1004 KB |
Output is correct |
34 |
Correct |
13 ms |
7148 KB |
Output is correct |
35 |
Correct |
852 ms |
72684 KB |
Output is correct |
36 |
Correct |
812 ms |
68716 KB |
Output is correct |
37 |
Correct |
789 ms |
67636 KB |
Output is correct |
38 |
Correct |
851 ms |
72556 KB |
Output is correct |
39 |
Correct |
1 ms |
364 KB |
Output is correct |
40 |
Correct |
3 ms |
876 KB |
Output is correct |
41 |
Correct |
3 ms |
876 KB |
Output is correct |
42 |
Correct |
3 ms |
876 KB |
Output is correct |
43 |
Correct |
3 ms |
1004 KB |
Output is correct |
44 |
Correct |
3 ms |
876 KB |
Output is correct |
45 |
Correct |
1 ms |
364 KB |
Output is correct |
46 |
Correct |
1 ms |
748 KB |
Output is correct |
47 |
Correct |
3 ms |
876 KB |
Output is correct |
48 |
Correct |
3 ms |
876 KB |
Output is correct |
49 |
Correct |
3 ms |
876 KB |
Output is correct |
50 |
Correct |
3 ms |
876 KB |
Output is correct |
51 |
Correct |
35 ms |
5356 KB |
Output is correct |
52 |
Correct |
37 ms |
5228 KB |
Output is correct |
53 |
Correct |
33 ms |
5248 KB |
Output is correct |
54 |
Correct |
35 ms |
5304 KB |
Output is correct |
55 |
Correct |
1 ms |
492 KB |
Output is correct |
56 |
Correct |
3 ms |
1900 KB |
Output is correct |
57 |
Correct |
2 ms |
1644 KB |
Output is correct |
58 |
Correct |
29 ms |
4588 KB |
Output is correct |
59 |
Correct |
32 ms |
5100 KB |
Output is correct |
60 |
Correct |
30 ms |
4588 KB |
Output is correct |
61 |
Correct |
33 ms |
5100 KB |
Output is correct |
62 |
Correct |
78 ms |
12524 KB |
Output is correct |
63 |
Correct |
78 ms |
12652 KB |
Output is correct |
64 |
Correct |
95 ms |
12768 KB |
Output is correct |
65 |
Correct |
343 ms |
40556 KB |
Output is correct |
66 |
Correct |
369 ms |
40940 KB |
Output is correct |
67 |
Correct |
12 ms |
7148 KB |
Output is correct |
68 |
Correct |
6 ms |
1004 KB |
Output is correct |
69 |
Correct |
671 ms |
69580 KB |
Output is correct |
70 |
Correct |
766 ms |
70636 KB |
Output is correct |
71 |
Correct |
853 ms |
72556 KB |
Output is correct |
72 |
Correct |
720 ms |
75404 KB |
Output is correct |
73 |
Correct |
819 ms |
69996 KB |
Output is correct |
74 |
Correct |
654 ms |
73836 KB |
Output is correct |
75 |
Correct |
783 ms |
68364 KB |
Output is correct |