Submission #352461

#	Time	Username	Problem	Language	Result	Execution time	Memory
352461		MatijaL	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	998 ms	147444 KiB

tickets

/**
 * Author: MatijaL
 * Time: 2021-01-17 18:15:39
**/
#include <tickets.h>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pll pair<ll, ll>
#define loop(i, n) for(ll i = 0; i < n; i++)
#define FOR(i,n,m) for(ll i = n; i <= m; i++)
#define isIn(vec, item) find(vec.begin(), vec.end(), item) != vec.end()
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define inf 1000000005
#define mod 1000000007
#define print(v) for(auto e : v) cout << e << " "; cout << endl;
#define limit 1600


ll find_maximum(int k, vector<vector<int>> x){
    ll n = x.size();
    ll m = x[0].size();
    
    int label[n][m];
    memset(label, 0, sizeof label);

    //daj minuse
    loop(i, n) loop(j, k) label[i][j] = -1;

    //povezave
    int d = m - k;
    vector<pair<int, pll>> v; //par<cost<i, j> >
    loop(i, n){
        loop(j, k){
            v.pb(mp(x[i][j+d] + x[i][j], mp(i, j)));
        }
    }

    sort(all(v));
    reverse(all(v));

    loop(i, (k*n)/2){
        auto e = v[i];
        pll c = e.sc;
        label[c.fs][c.sc] = 0;
        label[c.fs][c.sc+d] = 1;
    }
    
    vector<vector<int>> out (n, vector<int>(m, -1));
    ll ans = 0;
    int K = 0;
    loop(color, n){
        loop(i, m){
            if(label[color][i] != -1) break;
            out[color][i] = K;
            K++;
            K%=k;
            ans -= x[color][i];
        }
    }

    assert(K==0);
    K = k-1;
    loop(color, n){
        for(int i = m-1; i>=0; i--){
            if(label[color][i] != 1) break;
            out[color][i] = K;
            K--;
            if(K < 0) K+=k;
            ans += x[color][i];
        }
    }

    //assert(K==0);

    
    allocate_tickets(out);
    return ans;
}

• 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