Submission #1060260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060260		idas	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	565 ms	93720 KiB

tickets

#include "bits/stdc++.h"
#include "tickets.h"

#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define sz(x) ((int)(x).size())
#define pb push_back
#define s second
#define f first

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int N=1510;
int n, m, label[N][N];

long long find_maximum(int k, std::vector<std::vector<int>> x) {
    n=sz(x); m=sz(x[0]);
    ll ans=0;
    vector<pair<int,pair<int,pii>>> gain;
    FOR(i, 0, n) {
        for(int j=k-1; j>=0; j--) {
            label[i][j]=-1;
            ans-=x[i][j];
            int r=m-k+j, val=x[i][j]+x[i][r];
            gain.pb({val,{i,{j,r}}});
        }
    }
    sort(gain.begin(), gain.end());
    reverse(gain.begin(), gain.end());
    FOR(i, 0, n*k/2) {
        int val=gain[i].f, x=gain[i].s.f, y=gain[i].s.s.f, z=gain[i].s.s.s;
        label[x][y]=0; label[x][z]=1;
        ans+=val;
    }
    vector b(n, vector(m, -1));
    int in=0;
    FOR(i, 0, n) {
        int now=in;
        FOR(j, 0, m) {
            if(label[i][j]==-1) b[i][j]=now++, in=now%k;
            if(label[i][j]==1) b[i][j]=now++;
            now%=k;
        }
    }
    allocate_tickets(b);
    return ans;
}
/*
2 3 3
0 2 5
1 1 3

4 2 1
5 9
1 4
3 6
2 7

4 4 1
0 1 2 9
4 4 4 5
3 3 3 7
3 4 4 4

4 2 1
0 10
1 5
0 6
0 6

4 4 1
0 1 2 9
7 7 7 7
7 7 7 7
7 7 7 7

8 2 1
1 9
0 10
2 3
3 4
6 8
1 5
0 2
3 4

4 3 2
0 1 1
1 1 1
0 0 1
0 0 0

4 2 2
0 1
0 1
0 0
1 1

4 2 1
0 1
0 0
0 0
1 1

4 3 2
0 0 0
0 1 1
0 1 1
1 1 1
*/

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23
• Subtask 7: 10 / 10