Submission #1245417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245417		qwusha	Carnival Tickets (IOI20_tickets)	C++20	11 / 100	91 ms	9796 KiB

tickets

#include "tickets.h"

#include <iostream>
#include <bits/stdc++.h>

#define fi first
#define se second
typedef long long ll;
using namespace std;

int inf = 1e9 + 7;


ll result(vector<int> &s) {
    int m = s.size();
    sort(s.begin(), s.end());
    ll mid = s[m / 2];
    ll res = 0;
    for (auto el : s) {
        res += abs(mid - el);
    }
    return res;
}


ll find_maximum(int k, vector<vector<int>> x) {
    int n = x.size();
    vector<int> mini(n), maxi(n);
    vector<int> indmini(n), indmaxi(n);
    int m;
    for (int i = 0; i < n; i++) {
        m = x[i].size();
        int mi = inf, ma = -1;
        int indmi = -1, indma =-1;
        for (int j = 0; j < m; j++) {
            mi = min(mi, x[i][j]);
            ma = max(ma, x[i][j]);
            if (mi == x[i][j])
                indmi = j;
            if (ma == x[i][j])
                indma = j;
        }
        mini[i] = mi;
        indmini[i] = indmi;
        maxi[i] = ma;
        indmaxi[i] = indma;
    }
    vector<pair<vector<int>, vector<int>>> dp(n);
    vector<vector<int>> par(n, {-1,-1});
    dp[0].fi = {mini[0]};
    dp[0].se = {maxi[0]};
    vector<int> pr1, pr0;
    for (int i = 1; i < n; i++) {
        pr0 = dp[i - 1].fi;
        pr1 = dp[i - 1].se;
        pr0.push_back(mini[i]);
        pr1.push_back(mini[i]);
        if (result(pr0) > result(pr1)) {
            dp[i].fi = pr0;
            par[i][0] = 0;
        } else {
            dp[i].fi = pr1;
            par[i][0] = 1;
        }
        pr0 = dp[i - 1].fi;
        pr1 = dp[i - 1].se;
        pr0.push_back(maxi[i]);
        pr1.push_back(maxi[i]);
        if (result(pr0) > result(pr1)) {
            dp[i].se = pr0;
            par[i][1] = 0;
        } else {
            dp[i].se = pr1;
            par[i][1] = 1;
        }
    }
    ll res;
    int typ;
    int cur = n - 1;
    vector<vector<int>> s(n, vector<int>(m, -1));
    if (result(dp[n - 1].fi) > result(dp[n - 1].se)) {
        res = result(dp[n - 1].fi);
        typ = 0;
    } else {
        res = result(dp[n - 1].se);
        typ = 1;
    }
    while (cur != -1) {
        if (typ == 0) {
            s[cur][indmini[cur]] = 0;
        } else {
            s[cur][indmaxi[cur]] = 0;
        }
        typ = par[cur][typ];
        cur--;
    }
    allocate_tickets(s);
    return res;


}

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