#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include "tickets.h"
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
int n, m, kk;
vector<vector<int> > a;
int beg[1501], endi[1501];
vector<pii> subt;
set<pii> co, co2;
vector<pii> insback;
set<pii>:: iterator it, it2;
bool usedc[1501];
ll ansval=0;
vector<int> plamt;
vector<vector<int> > ans;
ll find_maximum(int kkk, vector<vector<int> > x)
{
int i, j;
n=x.size(), m=x[1].size(), kk=kkk;
a=x;
for(i=0;i<m;i++)
plamt.pb(-1);
for(i=0;i<n;i++)
ans.pb(plamt);
for(i=0;i<n;i++)
endi[i]=m-1;
for(i=0;i<n;i++){
for(j=0;j<kk;j++){
ansval+=a[i][endi[i]];
subt.pb({a[i][endi[i]]+a[i][kk-j-1], i});
endi[i]--;
}
}
sort(subt.begin(), subt.end());
for(i=0;i<n*kk/2;i++){
pii f=subt[i];
ansval-=f.first;
beg[f.second]++, endi[f.second]++;
}
for(i=0;i<n;i++){
co.insert({beg[i], i});
co2.insert({m-endi[i], i});
}
for(i=0;i<kk;i++){
for(j=0;j<n;j++)
usedc[j]=false;
insback.clear();
for(j=0;j<n/2;j++){
it=co.end(), it--;
pii f=*it;
co.erase(it);
f.first--;
ans[f.second][f.first]=i, usedc[f.second]=true;
insback.pb(f);
}
for(j=0;j<n/2;j++)
co.insert(insback[j]);
insback.clear();
j=0;
it=co2.end(), it--;
while(j<n/2){
if(!usedc[it->second]){
it2=it, it2--;
pii f=*it;
co2.erase(it);
f.first--;
ans[f.second][m-f.first]=i, usedc[f.second]=true;
insback.pb(f);
it=it2, j++;
}
else
it--;
}
for(j=0;j<n/2;j++)
co2.insert(insback[j]);
}
allocate_tickets(ans);
return ansval;
}
//int main()
//{
// int i, j;
//
// cin >> n >> m >> kk;
// for(i=0;i<m;i++)
// plamt.pb(0);
// for(i=0;i<n;i++)
// a.pb(plamt);
// plamt.clear();
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++){
// int x;
// cin >> x;
// a[i-1][j-1]=x;
// }
// find_maximum(kk, a);
//
// return 0;
//}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
512 KB |
Output is correct |
6 |
Correct |
3 ms |
1024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
3 ms |
512 KB |
Output is correct |
5 |
Correct |
31 ms |
2816 KB |
Output is correct |
6 |
Correct |
757 ms |
60520 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
3 ms |
512 KB |
Output is correct |
5 |
Correct |
32 ms |
3184 KB |
Output is correct |
6 |
Correct |
900 ms |
70388 KB |
Output is correct |
7 |
Correct |
885 ms |
73532 KB |
Output is correct |
8 |
Correct |
5 ms |
768 KB |
Output is correct |
9 |
Correct |
0 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
256 KB |
Output is correct |
11 |
Correct |
0 ms |
384 KB |
Output is correct |
12 |
Correct |
9 ms |
1024 KB |
Output is correct |
13 |
Correct |
30 ms |
2800 KB |
Output is correct |
14 |
Correct |
29 ms |
2928 KB |
Output is correct |
15 |
Correct |
923 ms |
76604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
512 KB |
Output is correct |
5 |
Correct |
50 ms |
3560 KB |
Output is correct |
6 |
Correct |
8 ms |
896 KB |
Output is correct |
7 |
Correct |
11 ms |
1280 KB |
Output is correct |
8 |
Correct |
1333 ms |
81212 KB |
Output is correct |
9 |
Correct |
1269 ms |
75556 KB |
Output is correct |
10 |
Correct |
1272 ms |
75808 KB |
Output is correct |
11 |
Correct |
1356 ms |
81092 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
3 ms |
512 KB |
Output is correct |
3 |
Correct |
3 ms |
512 KB |
Output is correct |
4 |
Correct |
3 ms |
512 KB |
Output is correct |
5 |
Correct |
3 ms |
512 KB |
Output is correct |
6 |
Correct |
5 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
512 KB |
Output is correct |
10 |
Correct |
4 ms |
512 KB |
Output is correct |
11 |
Correct |
4 ms |
512 KB |
Output is correct |
12 |
Correct |
4 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
3 ms |
512 KB |
Output is correct |
3 |
Correct |
3 ms |
512 KB |
Output is correct |
4 |
Correct |
3 ms |
512 KB |
Output is correct |
5 |
Correct |
3 ms |
512 KB |
Output is correct |
6 |
Correct |
5 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
512 KB |
Output is correct |
10 |
Correct |
4 ms |
512 KB |
Output is correct |
11 |
Correct |
4 ms |
512 KB |
Output is correct |
12 |
Correct |
4 ms |
512 KB |
Output is correct |
13 |
Correct |
33 ms |
2816 KB |
Output is correct |
14 |
Correct |
33 ms |
2808 KB |
Output is correct |
15 |
Correct |
41 ms |
3192 KB |
Output is correct |
16 |
Correct |
51 ms |
3564 KB |
Output is correct |
17 |
Correct |
1 ms |
384 KB |
Output is correct |
18 |
Correct |
4 ms |
640 KB |
Output is correct |
19 |
Correct |
2 ms |
512 KB |
Output is correct |
20 |
Correct |
39 ms |
3188 KB |
Output is correct |
21 |
Correct |
43 ms |
3188 KB |
Output is correct |
22 |
Correct |
46 ms |
3440 KB |
Output is correct |
23 |
Correct |
49 ms |
3440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
512 KB |
Output is correct |
6 |
Correct |
3 ms |
1024 KB |
Output is correct |
7 |
Correct |
0 ms |
256 KB |
Output is correct |
8 |
Correct |
0 ms |
256 KB |
Output is correct |
9 |
Correct |
0 ms |
384 KB |
Output is correct |
10 |
Correct |
3 ms |
512 KB |
Output is correct |
11 |
Correct |
31 ms |
2816 KB |
Output is correct |
12 |
Correct |
757 ms |
60520 KB |
Output is correct |
13 |
Correct |
1 ms |
256 KB |
Output is correct |
14 |
Correct |
0 ms |
256 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
3 ms |
512 KB |
Output is correct |
17 |
Correct |
32 ms |
3184 KB |
Output is correct |
18 |
Correct |
900 ms |
70388 KB |
Output is correct |
19 |
Correct |
885 ms |
73532 KB |
Output is correct |
20 |
Correct |
5 ms |
768 KB |
Output is correct |
21 |
Correct |
0 ms |
384 KB |
Output is correct |
22 |
Correct |
1 ms |
256 KB |
Output is correct |
23 |
Correct |
0 ms |
384 KB |
Output is correct |
24 |
Correct |
9 ms |
1024 KB |
Output is correct |
25 |
Correct |
30 ms |
2800 KB |
Output is correct |
26 |
Correct |
29 ms |
2928 KB |
Output is correct |
27 |
Correct |
923 ms |
76604 KB |
Output is correct |
28 |
Correct |
0 ms |
256 KB |
Output is correct |
29 |
Correct |
1 ms |
384 KB |
Output is correct |
30 |
Correct |
0 ms |
384 KB |
Output is correct |
31 |
Correct |
4 ms |
512 KB |
Output is correct |
32 |
Correct |
50 ms |
3560 KB |
Output is correct |
33 |
Correct |
8 ms |
896 KB |
Output is correct |
34 |
Correct |
11 ms |
1280 KB |
Output is correct |
35 |
Correct |
1333 ms |
81212 KB |
Output is correct |
36 |
Correct |
1269 ms |
75556 KB |
Output is correct |
37 |
Correct |
1272 ms |
75808 KB |
Output is correct |
38 |
Correct |
1356 ms |
81092 KB |
Output is correct |
39 |
Correct |
0 ms |
384 KB |
Output is correct |
40 |
Correct |
3 ms |
512 KB |
Output is correct |
41 |
Correct |
3 ms |
512 KB |
Output is correct |
42 |
Correct |
3 ms |
512 KB |
Output is correct |
43 |
Correct |
3 ms |
512 KB |
Output is correct |
44 |
Correct |
5 ms |
512 KB |
Output is correct |
45 |
Correct |
1 ms |
384 KB |
Output is correct |
46 |
Correct |
1 ms |
384 KB |
Output is correct |
47 |
Correct |
3 ms |
512 KB |
Output is correct |
48 |
Correct |
4 ms |
512 KB |
Output is correct |
49 |
Correct |
4 ms |
512 KB |
Output is correct |
50 |
Correct |
4 ms |
512 KB |
Output is correct |
51 |
Correct |
33 ms |
2816 KB |
Output is correct |
52 |
Correct |
33 ms |
2808 KB |
Output is correct |
53 |
Correct |
41 ms |
3192 KB |
Output is correct |
54 |
Correct |
51 ms |
3564 KB |
Output is correct |
55 |
Correct |
1 ms |
384 KB |
Output is correct |
56 |
Correct |
4 ms |
640 KB |
Output is correct |
57 |
Correct |
2 ms |
512 KB |
Output is correct |
58 |
Correct |
39 ms |
3188 KB |
Output is correct |
59 |
Correct |
43 ms |
3188 KB |
Output is correct |
60 |
Correct |
46 ms |
3440 KB |
Output is correct |
61 |
Correct |
49 ms |
3440 KB |
Output is correct |
62 |
Correct |
86 ms |
7160 KB |
Output is correct |
63 |
Correct |
90 ms |
7160 KB |
Output is correct |
64 |
Correct |
141 ms |
9444 KB |
Output is correct |
65 |
Correct |
460 ms |
31440 KB |
Output is correct |
66 |
Correct |
575 ms |
35928 KB |
Output is correct |
67 |
Correct |
11 ms |
1280 KB |
Output is correct |
68 |
Correct |
8 ms |
896 KB |
Output is correct |
69 |
Correct |
747 ms |
60792 KB |
Output is correct |
70 |
Correct |
1029 ms |
70220 KB |
Output is correct |
71 |
Correct |
1330 ms |
81128 KB |
Output is correct |
72 |
Correct |
1160 ms |
77588 KB |
Output is correct |
73 |
Correct |
1249 ms |
77156 KB |
Output is correct |
74 |
Correct |
912 ms |
68924 KB |
Output is correct |
75 |
Correct |
1027 ms |
68680 KB |
Output is correct |