Submission #1074798

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074798		Namviet2704	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	1066 ms	107424 KiB

tickets

#include<tickets.h>
#include<bits/stdc++.h>
#define xx second.first
#define yy second.second
#define fi first
#define se second
#define pii pair<int, pair<int, int>>
#define pi pair<int, int>
#define ll long long

using namespace std;

const int N = 1505;

vector<int> add[N], minu[N];

long long find_maximum(int k, vector<vector<int>> x)
{
    int n = x.size();
    int m = x[0].size();
    vector<vector<int>> ans;
    ans.resize(n);
    for(int i = 0; i < n; i++)
    {
        ans[i].resize(m);
        for(int j = 0; j < m; j++)
            ans[i][j] = -1;
    }
    priority_queue<pii, vector<pii>> q;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < k; j++)
            q.push({x[i][j] + x[i][m - k + j], {i, j}});
    ll kq = 0;
    for(int i = 0; i < n * k / 2; i++)
    {
        pii tmp = q.top();
        q.pop();
        kq += x[tmp.xx][m - k + tmp.yy];
        add[tmp.xx].push_back(m - k + tmp.yy);
//        cout << tmp.xx << '\n';
    }
    for(int i = 0; i < n * k / 2; i++)
    {
        pii tmp = q.top();
        q.pop();
        kq -= x[tmp.xx][tmp.yy];
        minu[tmp.xx].push_back(tmp.yy);
//        cout << tmp.xx << '\n';
    }
    for(int i = 0; i < k; i++)
    {
        priority_queue<pi, vector<pi>> tmp;
        for(int j = 0; j < n; j++)
            tmp.push({add[j].size(), j});
        for(int j = 0; j < n / 2; j++)
        {
            pi haha = tmp.top();
            ans[haha.se][add[haha.se].back()] = i;
            tmp.pop();
            add[haha.se].pop_back();
        }
        while(!tmp.empty())
        {
            pi haha = tmp.top();
            ans[haha.se][minu[haha.se].back()] = i;
            tmp.pop();
            minu[haha.se].pop_back();
        }
    }
//    cout << kq << '\n';
//    for(int i = 0; i < n; i++)
//    {
//        for(int j = 0; j < m; j++)
//            cout << ans[i][j] << " ";
//        cout << '\n';
//    }
    allocate_tickets(ans);
    return kq;
}

//int main ()
//{
//    ios_base::sync_with_stdio(0);
//    cin.tie(0), cout.tie(0);
//    int k = 2;
//    vector<vector<int>> huhu;
//    huhu.resize(2);
//    huhu[0] = {0, 2, 5};
//    huhu[1] = {1, 1, 3};
////    huhu[2] = {3, 6};
////    huhu[3] = {2, 7};
//    find_maximum(k, huhu);
//    return 0;
//}

• 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