Submission #305769

#	Time	Username	Problem	Language	Result	Execution time	Memory
305769		bruce_test	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	1071 ms	62500 KiB

tickets

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define lc (rt<<1)
#define rc (rt<<1|1)
#define pb push_back
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef vector<pi> vii;
typedef vector<pii> viii;
const int inf = 0x3F3F3F3F;
const ll infl = 0x3F3F3F3F3F3F3F3FLL;
const int mod = 1e9 + 7;
void allocate_tickets(vector<vi> s);
ll find_maximum(int k, vector<vi> x){
    int n = x.size(), m = x[0].size(); ll ans = 0;
    vector<vi> s(n, vi(m, -1)); vi f(n, 0), r(n, k-1);
    vector<pi> p;
    for(int i=0; i<n; i++){
        for(int j=0; j<k; j++){
            ans -= x[i][j];
            p.pb({x[i][j] + x[i][m-k+j], i});
        }
    }
    sort(p.begin(), p.end(), greater<pi>());
    for(int i=0, tot=n*k/2; i<tot; i++){
        ans += p[i].f; f[p[i].s]++; r[p[i].s]--;
    }
    for(int i=0, cnt=0; i<k; i++, cnt=0){
        for(int j=0; j<n; j++){
            if(!f[j]) {
                s[j][r[j]] = i; r[j]--;
            } else if(r[j] == -1) {
                s[j][m - f[j]] = i; f[j]--; cnt++;
            }
        }
        for(int j=0; j<n; j++){
            if(f[j] && r[j]!=-1){
                if(cnt < n/2) { s[j][m - f[j]] = i; f[j]--; cnt++; }
                else { s[j][r[j]] = i; r[j]--; }
            }
        }
    }
    allocate_tickets(s); return ans;
}
//void allocate_tickets(vector<vi> s){
//    for(int i=0; i<s.size(); i++){
//        for(int x: s[i]) cout << x << " ";
//        cout << endl;
//    }
//}
//int main(){
//    vector<vi> a = {{5, 9}, {1, 4}, {3, 6}, {2, 7}};
//    cout << find_maximum(1, a) << endl;
//}

• 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