#include "tickets.h"
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define lun(x) (int)x.size()
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<60);
const int inf=(1<<30);
const int nmax=2e3+50;
const ll mod=1e9+7;
using namespace std;
int n,m,i,j,nr,vz[nmax],t,l[nmax],r[nmax];
vector<vector<int> >rs;
vector<pair<int,pair<int,int> > >vc;
vector<int>v[2][nmax];
vector<pair<int,int> >ea,eb,fft;
set<pair<int,int> >s,b,st;
pair<int,int>pr;
set<pair<int,int> >::iterator it;
ll sm;
ll find_maximum(int k,vector<vector<int> > a)
{
n=lun(a),m=lun(a[0]);
for(i=0;i<n;i++)
{
l[i]=k-1;
r[i]=m-1;
st.in(mkp(a[i][l[i]]+a[i][r[i]],i));
}
for(i=0;i<n*k/2;i++)
{
pr=*(--st.end());
st.er(--st.end());
r[pr.sc]--,l[pr.sc]--;
if(l[pr.sc]>-1)st.in(mkp(a[pr.sc][l[pr.sc]]+a[pr.sc][r[pr.sc]],pr.sc));
}
for(i=0;i<n;i++)
{
for(j=0;j<=l[i];j++)vc.pb(mkp(a[i][j],mkp(i,j)));
for(j=r[i]+1;j<m;j++)vc.pb(mkp(a[i][j],mkp(i,j)));
}
sort(all(vc));
for(i=0;i<n*k;i++)
{
v[i<n*k/2][vc[i].sc.fr].pb(vc[i].sc.sc);
if(i<n*k/2)sm-=1LL*vc[i].fr;
else sm+=1LL*vc[i].fr;
}
for(i=0;i<n;i++)
{
if(!v[1][i].empty())s.in(mkp(lun(v[1][i]),i));
}
rs.resize(n);
for(i=0;i<n;i++)for(j=0;j<m;j++)rs[i].pb(-1);
for(i=0;i<k;i++)
{
ea.clear();
it=--s.end();
for(j=0;j<n/2;j++)
{
t=it->sc;
rs[t][v[1][t].back()]=i;
v[1][t].pop_back();
vz[t]=1;
ea.pb(*it);
it--;
}
for(j=0;j<n;j++)
{
if(!vz[j])
{
rs[j][v[0][j].back()]=i;
v[0][j].pop_back();
}
vz[j]=0;
}
for(j=0;j<lun(ea);j++)
{
s.er(s.fd(ea[j]));
if(ea[j].fr>1)s.in(mkp(ea[j].fr-1,ea[j].sc));
}
}
allocate_tickets(rs);
return sm;
}
/*int main()
{
//freopen("sol.in","r",stdin);
//freopen("sol.out","w",stdout);
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
return 0;
}*/
# |
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 |
492 KB |
Output is correct |
5 |
Correct |
1 ms |
492 KB |
Output is correct |
6 |
Correct |
2 ms |
1004 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 |
620 KB |
Output is correct |
5 |
Correct |
27 ms |
2816 KB |
Output is correct |
6 |
Correct |
667 ms |
55056 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 |
748 KB |
Output is correct |
5 |
Correct |
36 ms |
3944 KB |
Output is correct |
6 |
Correct |
1076 ms |
79648 KB |
Output is correct |
7 |
Correct |
1039 ms |
86344 KB |
Output is correct |
8 |
Correct |
6 ms |
940 KB |
Output is correct |
9 |
Correct |
1 ms |
492 KB |
Output is correct |
10 |
Correct |
1 ms |
492 KB |
Output is correct |
11 |
Correct |
1 ms |
492 KB |
Output is correct |
12 |
Correct |
10 ms |
1324 KB |
Output is correct |
13 |
Correct |
33 ms |
3432 KB |
Output is correct |
14 |
Correct |
46 ms |
3432 KB |
Output is correct |
15 |
Correct |
1091 ms |
91988 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 |
5 ms |
748 KB |
Output is correct |
5 |
Correct |
55 ms |
4580 KB |
Output is correct |
6 |
Correct |
8 ms |
1068 KB |
Output is correct |
7 |
Correct |
12 ms |
1456 KB |
Output is correct |
8 |
Correct |
1567 ms |
97268 KB |
Output is correct |
9 |
Correct |
1510 ms |
92172 KB |
Output is correct |
10 |
Correct |
1452 ms |
90612 KB |
Output is correct |
11 |
Correct |
1578 ms |
97140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
3 ms |
620 KB |
Output is correct |
3 |
Correct |
3 ms |
620 KB |
Output is correct |
4 |
Correct |
3 ms |
620 KB |
Output is correct |
5 |
Correct |
4 ms |
620 KB |
Output is correct |
6 |
Correct |
4 ms |
748 KB |
Output is correct |
7 |
Correct |
1 ms |
492 KB |
Output is correct |
8 |
Correct |
1 ms |
492 KB |
Output is correct |
9 |
Correct |
4 ms |
620 KB |
Output is correct |
10 |
Correct |
4 ms |
620 KB |
Output is correct |
11 |
Correct |
4 ms |
748 KB |
Output is correct |
12 |
Correct |
4 ms |
748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
3 ms |
620 KB |
Output is correct |
3 |
Correct |
3 ms |
620 KB |
Output is correct |
4 |
Correct |
3 ms |
620 KB |
Output is correct |
5 |
Correct |
4 ms |
620 KB |
Output is correct |
6 |
Correct |
4 ms |
748 KB |
Output is correct |
7 |
Correct |
1 ms |
492 KB |
Output is correct |
8 |
Correct |
1 ms |
492 KB |
Output is correct |
9 |
Correct |
4 ms |
620 KB |
Output is correct |
10 |
Correct |
4 ms |
620 KB |
Output is correct |
11 |
Correct |
4 ms |
748 KB |
Output is correct |
12 |
Correct |
4 ms |
748 KB |
Output is correct |
13 |
Correct |
28 ms |
2796 KB |
Output is correct |
14 |
Correct |
29 ms |
2796 KB |
Output is correct |
15 |
Correct |
43 ms |
3688 KB |
Output is correct |
16 |
Correct |
55 ms |
4580 KB |
Output is correct |
17 |
Correct |
2 ms |
492 KB |
Output is correct |
18 |
Correct |
4 ms |
748 KB |
Output is correct |
19 |
Correct |
2 ms |
620 KB |
Output is correct |
20 |
Correct |
44 ms |
3816 KB |
Output is correct |
21 |
Correct |
45 ms |
3812 KB |
Output is correct |
22 |
Correct |
53 ms |
4324 KB |
Output is correct |
23 |
Correct |
52 ms |
4192 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 |
492 KB |
Output is correct |
5 |
Correct |
1 ms |
492 KB |
Output is correct |
6 |
Correct |
2 ms |
1004 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 |
620 KB |
Output is correct |
11 |
Correct |
27 ms |
2816 KB |
Output is correct |
12 |
Correct |
667 ms |
55056 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 |
3 ms |
748 KB |
Output is correct |
17 |
Correct |
36 ms |
3944 KB |
Output is correct |
18 |
Correct |
1076 ms |
79648 KB |
Output is correct |
19 |
Correct |
1039 ms |
86344 KB |
Output is correct |
20 |
Correct |
6 ms |
940 KB |
Output is correct |
21 |
Correct |
1 ms |
492 KB |
Output is correct |
22 |
Correct |
1 ms |
492 KB |
Output is correct |
23 |
Correct |
1 ms |
492 KB |
Output is correct |
24 |
Correct |
10 ms |
1324 KB |
Output is correct |
25 |
Correct |
33 ms |
3432 KB |
Output is correct |
26 |
Correct |
46 ms |
3432 KB |
Output is correct |
27 |
Correct |
1091 ms |
91988 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 |
5 ms |
748 KB |
Output is correct |
32 |
Correct |
55 ms |
4580 KB |
Output is correct |
33 |
Correct |
8 ms |
1068 KB |
Output is correct |
34 |
Correct |
12 ms |
1456 KB |
Output is correct |
35 |
Correct |
1567 ms |
97268 KB |
Output is correct |
36 |
Correct |
1510 ms |
92172 KB |
Output is correct |
37 |
Correct |
1452 ms |
90612 KB |
Output is correct |
38 |
Correct |
1578 ms |
97140 KB |
Output is correct |
39 |
Correct |
1 ms |
364 KB |
Output is correct |
40 |
Correct |
3 ms |
620 KB |
Output is correct |
41 |
Correct |
3 ms |
620 KB |
Output is correct |
42 |
Correct |
3 ms |
620 KB |
Output is correct |
43 |
Correct |
4 ms |
620 KB |
Output is correct |
44 |
Correct |
4 ms |
748 KB |
Output is correct |
45 |
Correct |
1 ms |
492 KB |
Output is correct |
46 |
Correct |
1 ms |
492 KB |
Output is correct |
47 |
Correct |
4 ms |
620 KB |
Output is correct |
48 |
Correct |
4 ms |
620 KB |
Output is correct |
49 |
Correct |
4 ms |
748 KB |
Output is correct |
50 |
Correct |
4 ms |
748 KB |
Output is correct |
51 |
Correct |
28 ms |
2796 KB |
Output is correct |
52 |
Correct |
29 ms |
2796 KB |
Output is correct |
53 |
Correct |
43 ms |
3688 KB |
Output is correct |
54 |
Correct |
55 ms |
4580 KB |
Output is correct |
55 |
Correct |
2 ms |
492 KB |
Output is correct |
56 |
Correct |
4 ms |
748 KB |
Output is correct |
57 |
Correct |
2 ms |
620 KB |
Output is correct |
58 |
Correct |
44 ms |
3816 KB |
Output is correct |
59 |
Correct |
45 ms |
3812 KB |
Output is correct |
60 |
Correct |
53 ms |
4324 KB |
Output is correct |
61 |
Correct |
52 ms |
4192 KB |
Output is correct |
62 |
Correct |
79 ms |
8684 KB |
Output is correct |
63 |
Correct |
81 ms |
8812 KB |
Output is correct |
64 |
Correct |
159 ms |
13268 KB |
Output is correct |
65 |
Correct |
477 ms |
42324 KB |
Output is correct |
66 |
Correct |
664 ms |
51012 KB |
Output is correct |
67 |
Correct |
12 ms |
1584 KB |
Output is correct |
68 |
Correct |
8 ms |
1196 KB |
Output is correct |
69 |
Correct |
693 ms |
76976 KB |
Output is correct |
70 |
Correct |
1135 ms |
97448 KB |
Output is correct |
71 |
Correct |
1582 ms |
119028 KB |
Output is correct |
72 |
Correct |
1342 ms |
101924 KB |
Output is correct |
73 |
Correct |
1426 ms |
113536 KB |
Output is correct |
74 |
Correct |
1033 ms |
83748 KB |
Output is correct |
75 |
Correct |
1115 ms |
95528 KB |
Output is correct |