oj.uz

Submission #864816

# Submission time Handle Problem Language Result Execution time Memory
864816 2023-10-23T16:35:30 Z andrei_boaca Carnival Tickets (IOI20_tickets) C++17
62 / 100
 3000 ms 106832 KB 
#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];
int flow;
ll k;
bool flux()
{
    for(int i=0;i<=nodes;i++)
    {
        dist[i]=INF;
        from[i]=-1;
    }
    dist[S]=0;
    queue<int> coada;
    coada.push(S);
    while(!coada.empty())
    {
        ll nod=coada.front();
        coada.pop();
        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(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=-ans;
    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;
                r[i]--;
            }
            else
            {
                assert(cap[i][mns]>0);
                cap[i][mns]--;
                sol[i][l[i]]=pas;
                l[i]++;
            }
        }
    }
    allocate_tickets(sol);
	return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 5 ms 6776 KB Output is correct
6 Correct 105 ms 25612 KB Output is correct

Subtask #2
16.0 / 16.0

# 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 2 ms 2652 KB Output is correct
5 Correct 21 ms 9820 KB Output is correct
6 Correct 528 ms 106832 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2540 KB Output is correct
4 Correct 8 ms 2652 KB Output is correct
5 Correct 315 ms 9088 KB Output is correct
6 Execution timed out 3050 ms 65188 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 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 2536 KB Output is correct
4 Correct 29 ms 2652 KB Output is correct
5 Correct 1638 ms 10040 KB Output is correct
6 Correct 12 ms 2908 KB Output is correct
7 Correct 1607 ms 25844 KB Output is correct
8 Execution timed out 3101 ms 82344 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2808 KB Output is correct
3 Correct 3 ms 2652 KB Output is correct
4 Correct 9 ms 2760 KB Output is correct
5 Correct 15 ms 2652 KB Output is correct
6 Correct 23 ms 2748 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 3 ms 2396 KB Output is correct
9 Correct 17 ms 2652 KB Output is correct
10 Correct 20 ms 2652 KB Output is correct
11 Correct 22 ms 2716 KB Output is correct
12 Correct 24 ms 2652 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2808 KB Output is correct
3 Correct 3 ms 2652 KB Output is correct
4 Correct 9 ms 2760 KB Output is correct
5 Correct 15 ms 2652 KB Output is correct
6 Correct 23 ms 2748 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 3 ms 2396 KB Output is correct
9 Correct 17 ms 2652 KB Output is correct
10 Correct 20 ms 2652 KB Output is correct
11 Correct 22 ms 2716 KB Output is correct
12 Correct 24 ms 2652 KB Output is correct
13 Correct 25 ms 9820 KB Output is correct
14 Correct 72 ms 9868 KB Output is correct
15 Correct 817 ms 9784 KB Output is correct
16 Correct 1592 ms 10068 KB Output is correct
17 Correct 2 ms 2648 KB Output is correct
18 Correct 41 ms 6748 KB Output is correct
19 Correct 24 ms 6808 KB Output is correct
20 Correct 828 ms 9188 KB Output is correct
21 Correct 1004 ms 9712 KB Output is correct
22 Correct 1057 ms 9188 KB Output is correct
23 Correct 1497 ms 9720 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 5 ms 6776 KB Output is correct
6 Correct 105 ms 25612 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 21 ms 9820 KB Output is correct
12 Correct 528 ms 106832 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2540 KB Output is correct
16 Correct 8 ms 2652 KB Output is correct
17 Correct 315 ms 9088 KB Output is correct
18 Execution timed out 3050 ms 65188 KB Time limit exceeded
19 Halted 0 ms 0 KB -