#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
//#include "grader.cpp"
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];
vector<ll> muchii[2005];
bool use[2005];
int flow;
ll k;
bool flux()
{
for(int i=0;i<=nodes;i++)
{
dist[i]=INF;
from[i]=-1;
use[i]=0;
}
dist[S]=0;
priority_queue<pll,vector<pll>, greater<pll>> coada;
coada.push({0,S});
while(!coada.empty())
{
ll nod=coada.top().second;
coada.pop();
if(use[nod])
continue;
use[nod]=1;
for(int i:muchii[nod])
if(cap[nod][i]>0)
{
ll cost=0;
if(nod==mns)
{
if(i>=0&&i<n)
cost=-v[i][m-(k-cap[nod][i])-1];
}
if(nod==pls)
{
if(i>=0&&i<n)
cost=v[i][k-cap[nod][i]];
}
if(nod>=0&&nod<n)
{
if(i==mns)
cost=v[nod][m-cap[nod][i]];
if(i==pls)
cost=-v[nod][cap[nod][i]-1];
}
if(dist[i]>dist[nod]+cost)
{
dist[i]=dist[nod]+cost;
from[i]=nod;
coada.push({dist[i],i});
}
}
}
if(dist[D]==INF)
return 0;
flow++;
ans+=dist[D];
//cout<<flow<<' '<<ans<<'\n';
for(int i=D;i!=S;i=from[i])
{
cap[from[i]][i]--;
cap[i][from[i]]++;
}
return 1;
}
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;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
sol[i][j]=-1;
S=n;
D=n+1;
pls=n+2;
mns=n+3;
nodes=n+3;
muchii[S].push_back(pls);
muchii[pls].push_back(S);
muchii[S].push_back(mns);
muchii[mns].push_back(S);
cap[S][pls]=k*n/2;
cap[S][mns]=k*n/2;
for(int i=0;i<n;i++)
{
muchii[pls].push_back(i);
muchii[i].push_back(pls);
cap[pls][i]=k;
muchii[mns].push_back(i);
muchii[i].push_back(mns);
cap[mns][i]=k;
muchii[i].push_back(D);
muchii[D].push_back(i);
cap[i][D]=k;
}
while(flux());
ans=0;
for(int i=0;i<n;i++)
{
l[i]=0;
r[i]=m-1;
}
for(int i=0;i<n;i++)
swap(cap[i][pls],cap[i][mns]);
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;
ans+=v[i][r[i]];
r[i]--;
}
else
{
assert(cap[i][mns]>0);
cap[i][mns]--;
sol[i][l[i]]=pas;
ans-=v[i][l[i]];
l[i]++;
}
}
}
allocate_tickets(sol);
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2648 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2396 KB |
Output is correct |
5 |
Correct |
14 ms |
6800 KB |
Output is correct |
6 |
Correct |
393 ms |
25720 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
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 |
3 ms |
2648 KB |
Output is correct |
5 |
Correct |
30 ms |
9824 KB |
Output is correct |
6 |
Correct |
813 ms |
97660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
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 |
16 ms |
2648 KB |
Output is correct |
5 |
Correct |
895 ms |
9108 KB |
Output is correct |
6 |
Execution timed out |
3034 ms |
64512 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3031 ms |
2392 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3078 ms |
2392 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3078 ms |
2392 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2648 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2396 KB |
Output is correct |
5 |
Correct |
14 ms |
6800 KB |
Output is correct |
6 |
Correct |
393 ms |
25720 KB |
Output is correct |
7 |
Correct |
1 ms |
2392 KB |
Output is correct |
8 |
Correct |
1 ms |
2396 KB |
Output is correct |
9 |
Correct |
1 ms |
2396 KB |
Output is correct |
10 |
Correct |
3 ms |
2648 KB |
Output is correct |
11 |
Correct |
30 ms |
9824 KB |
Output is correct |
12 |
Correct |
813 ms |
97660 KB |
Output is correct |
13 |
Correct |
1 ms |
2396 KB |
Output is correct |
14 |
Correct |
1 ms |
2396 KB |
Output is correct |
15 |
Correct |
1 ms |
2396 KB |
Output is correct |
16 |
Correct |
16 ms |
2648 KB |
Output is correct |
17 |
Correct |
895 ms |
9108 KB |
Output is correct |
18 |
Execution timed out |
3034 ms |
64512 KB |
Time limit exceeded |
19 |
Halted |
0 ms |
0 KB |
- |