#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
//#include "grader.cpp"
/*#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")*/
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll INF=1e18;
ll ans=0;
int n,m;
vector<vector<int>> sol,v;
bool comp(pll a, pll b)
{
return a.second>b.second;
}
int S,D,mns,pls;
ll cap[2005][2005],nodes,dist[2005],from[2005],l[2005],r[2005],nr1[2005],nr0[2005],maxi[2005];
vector<ll> muchii[2005];
int use[2005];
int flow;
bool sub3;
ll k;
bool byplus(int a,int b)
{
return cap[a][pls]>cap[b][pls];
}
long long find_maximum(int K, std::vector<std::vector<int>> vectoras)
{
k=K;
n = vectoras.size();
m = vectoras[0].size();
sol=vectoras;
v=vectoras;
sub3=1;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
sol[i][j]=-1;
if(v[i][j]>1)
sub3=0;
}
pls=0;
mns=1;
ll ans=0;
multiset<pll> s;
for(int i=0;i<n;i++)
{
l[i]=k-1;
r[i]=m;
cap[i][mns]=k;
cap[i][pls]=0;
for(int j=0;j<k;j++)
ans-=v[i][j];
s.insert({v[i][r[i]-1]+v[i][l[i]],i});
}
for(int pas=0;pas<k*n/2;pas++)
{
auto it=prev(s.end());
int i=(*it).second;
cap[i][mns]--;
cap[i][pls]++;
ans+=v[i][r[i]-1]+v[i][l[i]];
r[i]--;
l[i]--;
s.erase(it);
if(cap[i][mns]>0)
s.insert({v[i][r[i]-1]+v[i][l[i]],i});
}
for(int i=0;i<n;i++)
{
l[i]=0;
r[i]=m-1;
}
for(int pas=0;pas<k;pas++)
{
vector<int> linii;
for(int i=0;i<n;i++)
linii.push_back(i);
sort(linii.begin(),linii.end(),byplus);
for(int z=0;z<n;z++)
{
int i=linii[z];
if(z<n/2)
{
assert(cap[i][pls]>0);
cap[i][pls]--;
sol[i][r[i]]=pas;
r[i]--;
}
else
{
assert(cap[i][mns]>0);
cap[i][mns]--;
sol[i][l[i]]=pas;
l[i]++;
}
}
}
allocate_tickets(sol);
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
0 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2396 KB |
Output is correct |
5 |
Correct |
1 ms |
6748 KB |
Output is correct |
6 |
Correct |
4 ms |
25692 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
2 ms |
2652 KB |
Output is correct |
5 |
Correct |
17 ms |
9008 KB |
Output is correct |
6 |
Correct |
416 ms |
85288 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2408 KB |
Output is correct |
3 |
Correct |
1 ms |
2544 KB |
Output is correct |
4 |
Correct |
2 ms |
2652 KB |
Output is correct |
5 |
Correct |
19 ms |
9124 KB |
Output is correct |
6 |
Correct |
434 ms |
90500 KB |
Output is correct |
7 |
Correct |
452 ms |
90724 KB |
Output is correct |
8 |
Correct |
2 ms |
2648 KB |
Output is correct |
9 |
Correct |
1 ms |
2396 KB |
Output is correct |
10 |
Correct |
1 ms |
2396 KB |
Output is correct |
11 |
Correct |
1 ms |
2396 KB |
Output is correct |
12 |
Correct |
5 ms |
5260 KB |
Output is correct |
13 |
Correct |
15 ms |
10856 KB |
Output is correct |
14 |
Correct |
17 ms |
6744 KB |
Output is correct |
15 |
Correct |
440 ms |
91472 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
2 ms |
2556 KB |
Output is correct |
5 |
Correct |
25 ms |
9868 KB |
Output is correct |
6 |
Correct |
4 ms |
2908 KB |
Output is correct |
7 |
Correct |
9 ms |
25948 KB |
Output is correct |
8 |
Correct |
650 ms |
109700 KB |
Output is correct |
9 |
Correct |
649 ms |
104192 KB |
Output is correct |
10 |
Correct |
600 ms |
102104 KB |
Output is correct |
11 |
Correct |
639 ms |
109652 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
2396 KB |
Output is correct |
2 |
Correct |
2 ms |
2652 KB |
Output is correct |
3 |
Correct |
2 ms |
2648 KB |
Output is correct |
4 |
Correct |
2 ms |
2652 KB |
Output is correct |
5 |
Correct |
2 ms |
2612 KB |
Output is correct |
6 |
Correct |
2 ms |
2648 KB |
Output is correct |
7 |
Correct |
1 ms |
2396 KB |
Output is correct |
8 |
Correct |
1 ms |
2396 KB |
Output is correct |
9 |
Correct |
2 ms |
2652 KB |
Output is correct |
10 |
Correct |
2 ms |
2652 KB |
Output is correct |
11 |
Correct |
2 ms |
2652 KB |
Output is correct |
12 |
Correct |
3 ms |
2648 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
2396 KB |
Output is correct |
2 |
Correct |
2 ms |
2652 KB |
Output is correct |
3 |
Correct |
2 ms |
2648 KB |
Output is correct |
4 |
Correct |
2 ms |
2652 KB |
Output is correct |
5 |
Correct |
2 ms |
2612 KB |
Output is correct |
6 |
Correct |
2 ms |
2648 KB |
Output is correct |
7 |
Correct |
1 ms |
2396 KB |
Output is correct |
8 |
Correct |
1 ms |
2396 KB |
Output is correct |
9 |
Correct |
2 ms |
2652 KB |
Output is correct |
10 |
Correct |
2 ms |
2652 KB |
Output is correct |
11 |
Correct |
2 ms |
2652 KB |
Output is correct |
12 |
Correct |
3 ms |
2648 KB |
Output is correct |
13 |
Correct |
19 ms |
9868 KB |
Output is correct |
14 |
Correct |
17 ms |
9816 KB |
Output is correct |
15 |
Correct |
20 ms |
9820 KB |
Output is correct |
16 |
Correct |
24 ms |
9812 KB |
Output is correct |
17 |
Correct |
1 ms |
2396 KB |
Output is correct |
18 |
Correct |
2 ms |
6748 KB |
Output is correct |
19 |
Correct |
2 ms |
6656 KB |
Output is correct |
20 |
Correct |
20 ms |
9248 KB |
Output is correct |
21 |
Correct |
21 ms |
9816 KB |
Output is correct |
22 |
Correct |
22 ms |
9184 KB |
Output is correct |
23 |
Correct |
32 ms |
9832 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
0 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2396 KB |
Output is correct |
5 |
Correct |
1 ms |
6748 KB |
Output is correct |
6 |
Correct |
4 ms |
25692 KB |
Output is correct |
7 |
Correct |
1 ms |
2396 KB |
Output is correct |
8 |
Correct |
1 ms |
2396 KB |
Output is correct |
9 |
Correct |
1 ms |
2396 KB |
Output is correct |
10 |
Correct |
2 ms |
2652 KB |
Output is correct |
11 |
Correct |
17 ms |
9008 KB |
Output is correct |
12 |
Correct |
416 ms |
85288 KB |
Output is correct |
13 |
Correct |
0 ms |
2396 KB |
Output is correct |
14 |
Correct |
1 ms |
2408 KB |
Output is correct |
15 |
Correct |
1 ms |
2544 KB |
Output is correct |
16 |
Correct |
2 ms |
2652 KB |
Output is correct |
17 |
Correct |
19 ms |
9124 KB |
Output is correct |
18 |
Correct |
434 ms |
90500 KB |
Output is correct |
19 |
Correct |
452 ms |
90724 KB |
Output is correct |
20 |
Correct |
2 ms |
2648 KB |
Output is correct |
21 |
Correct |
1 ms |
2396 KB |
Output is correct |
22 |
Correct |
1 ms |
2396 KB |
Output is correct |
23 |
Correct |
1 ms |
2396 KB |
Output is correct |
24 |
Correct |
5 ms |
5260 KB |
Output is correct |
25 |
Correct |
15 ms |
10856 KB |
Output is correct |
26 |
Correct |
17 ms |
6744 KB |
Output is correct |
27 |
Correct |
440 ms |
91472 KB |
Output is correct |
28 |
Correct |
1 ms |
2392 KB |
Output is correct |
29 |
Correct |
1 ms |
2396 KB |
Output is correct |
30 |
Correct |
1 ms |
2396 KB |
Output is correct |
31 |
Correct |
2 ms |
2556 KB |
Output is correct |
32 |
Correct |
25 ms |
9868 KB |
Output is correct |
33 |
Correct |
4 ms |
2908 KB |
Output is correct |
34 |
Correct |
9 ms |
25948 KB |
Output is correct |
35 |
Correct |
650 ms |
109700 KB |
Output is correct |
36 |
Correct |
649 ms |
104192 KB |
Output is correct |
37 |
Correct |
600 ms |
102104 KB |
Output is correct |
38 |
Correct |
639 ms |
109652 KB |
Output is correct |
39 |
Correct |
0 ms |
2396 KB |
Output is correct |
40 |
Correct |
2 ms |
2652 KB |
Output is correct |
41 |
Correct |
2 ms |
2648 KB |
Output is correct |
42 |
Correct |
2 ms |
2652 KB |
Output is correct |
43 |
Correct |
2 ms |
2612 KB |
Output is correct |
44 |
Correct |
2 ms |
2648 KB |
Output is correct |
45 |
Correct |
1 ms |
2396 KB |
Output is correct |
46 |
Correct |
1 ms |
2396 KB |
Output is correct |
47 |
Correct |
2 ms |
2652 KB |
Output is correct |
48 |
Correct |
2 ms |
2652 KB |
Output is correct |
49 |
Correct |
2 ms |
2652 KB |
Output is correct |
50 |
Correct |
3 ms |
2648 KB |
Output is correct |
51 |
Correct |
19 ms |
9868 KB |
Output is correct |
52 |
Correct |
17 ms |
9816 KB |
Output is correct |
53 |
Correct |
20 ms |
9820 KB |
Output is correct |
54 |
Correct |
24 ms |
9812 KB |
Output is correct |
55 |
Correct |
1 ms |
2396 KB |
Output is correct |
56 |
Correct |
2 ms |
6748 KB |
Output is correct |
57 |
Correct |
2 ms |
6656 KB |
Output is correct |
58 |
Correct |
20 ms |
9248 KB |
Output is correct |
59 |
Correct |
21 ms |
9816 KB |
Output is correct |
60 |
Correct |
22 ms |
9184 KB |
Output is correct |
61 |
Correct |
32 ms |
9832 KB |
Output is correct |
62 |
Correct |
46 ms |
17680 KB |
Output is correct |
63 |
Correct |
46 ms |
17688 KB |
Output is correct |
64 |
Correct |
66 ms |
17832 KB |
Output is correct |
65 |
Correct |
242 ms |
53840 KB |
Output is correct |
66 |
Correct |
269 ms |
54104 KB |
Output is correct |
67 |
Correct |
8 ms |
25948 KB |
Output is correct |
68 |
Correct |
4 ms |
2908 KB |
Output is correct |
69 |
Correct |
409 ms |
106900 KB |
Output is correct |
70 |
Correct |
543 ms |
107804 KB |
Output is correct |
71 |
Correct |
620 ms |
109856 KB |
Output is correct |
72 |
Correct |
508 ms |
93956 KB |
Output is correct |
73 |
Correct |
593 ms |
106636 KB |
Output is correct |
74 |
Correct |
447 ms |
92372 KB |
Output is correct |
75 |
Correct |
506 ms |
105196 KB |
Output is correct |