Submission #414059

#	Time	Username	Problem	Language	Result	Execution time	Memory
414059		Odavey	Carnival Tickets (IOI20_tickets)	C++14	27 / 100	625 ms	73128 KiB

tickets

//
// ~oisín~ C++ Template
//

#include                <bits/stdc++.h>
#define MX_N            5001
#define mp              make_pair
#define mod7            1000000007
#define modpi           314159
#define PI              3.141592653589793238
#define pb              push_back
#define FastIO          ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define All(a)          a.begin(),a.end()
#define fi              first
#define se              second
#define ll              long long int
#define ull             unsigned long long int

int kx[8]  =            {+2, +2, -2, -2, +1, +1, -1, -1};
int ky[8]  =            {+1, -1, +1, -1, +2, -2, +2, -2};
int d9x[9] =            {+1, +1, +1, +0, +0, +0, -1, -1, -1};
int d9y[9] =            {+1, +0, -1, +1, +0, -1, +1, +0, -1};
int dx4[4] =            {+0, +0, +1, -1};
int dy4[4] =            {+1, -1, +0, +0};

ll gcd(ull a, ull b){
    return (a==0)?b:gcd(b%a,a);
}

ll lcm(ull a, ull b){
    return a*(b/gcd(a,b));
}

const long long INF = 1e18;

using namespace std;

void allocate_tickets(vector<vector<int> > s);

//void allocate_tickets(vector<vector<int> > s){
//    for(vector<int>& v : s){
//        for(int x : v){
//            cout << x << ' ';
//        }
//        cout << endl;
//    }
//    cout << endl;
//    return;
//}

ll find_maximum(int k, vector<vector<int> > x){
    int n = x.size();
    int m = x[0].size();
    int U[n], L[n];
    pair<int, int> rows[n];//delta, id
    for(int i=0;i<n;++i){
        int lo = x[i][0];
        int hi = x[i][0];
        U[i] = 0;
        L[i] = 0;
        for(int j=1;j<m;++j){
            if(x[i][j] < lo){
                L[i] = j;
                lo = x[i][j];
            }
            if(x[i][j] > hi){
                U[i] = j;
                hi = x[i][j];
            }
        }
        rows[i] = {lo+hi, i};
    }
    sort(rows, rows+n);
    reverse(rows, rows+n);
    vector<vector<int> > ans;
    for(int i=0;i<n;++i){
        vector<int> tmp;
        for(int j=0;j<m;++j){
            tmp.pb(-1);
        }
        ans.pb(tmp);
    }
    ll res = 0ll;
    for(int i=0;i<n/2;++i){
        int id = rows[i].se;
        ans[id][U[id]] = 0;
        res += x[id][U[id]];
    }
    for(int i=(n/2);i<n;++i){
        int id = rows[i].se;
        ans[id][L[id]] = 0;
        res -= x[id][L[id]];
    }
    allocate_tickets(ans);
    return res;
}

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