Submission #747133

#	Time	Username	Problem	Language	Result	Execution time	Memory
747133		Rafi22	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	737 ms	84084 KiB

tickets

#include <bits/stdc++.h>
#include "tickets.h"

using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

/*void allocate_tickets(vector<vector<int>>r)
{
    int n=sz(r),m=sz(r[0]);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++) cout<<r[i][j]<<" ";
        cout<<endl;
    }
}
*/
ll find_maximum(int k,vector<vector<int>>a)
{
    int n=sz(a),m=sz(a[0]);
    vector<pair<int,int>>V;
    vector<vector<int>>r(n,vector<int>(m,-1));
    ll ans=0;
    for(int i=0;i<n;i++)
    {
        for(int j=m-k;j<m;j++) ans+=(ll)a[i][j];
        for(int j=0;j<k;j++) V.pb({-a[i][j]-a[i][j+m-k],i});
    }
    sort(all(V),greater<pair<int,int>>());
    vector<int>X(n,-1);
    vector<int>Y(n,m-k);
    int ile=n*k/2;
    for(auto [x,i]:V)
    {
        if(X[i]==k-1) continue;
        ans+=(ll)x;
        X[i]++;
        Y[i]++;
        ile--;
        if(ile==0) break;
    }
    for(int j=0;j<k;j++)
    {
        int c1=n/2,c2=n/2;
        for(int i=0;i<n;i++)
        {
            if(X[i]==-1)
            {
                c2--;
                r[i][Y[i]]=j;
                Y[i]++;
            }
            else if(Y[i]==m)
            {
                c1--;
                r[i][X[i]]=j;
                X[i]--;
            }
        }
        for(int i=0;i<n;i++)
        {
            if(X[i]==-1||Y[i]==m) continue;
            if(c1>0)
            {
                c1--;
                r[i][X[i]]=j;
                X[i]--;
            }
            else
            {
                c2--;
                r[i][Y[i]]=j;
                Y[i]++;
            }
        }
    }
    allocate_tickets(r);
    return ans;
}

/*int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout<<find_maximum(1, {{5, 9,10}, {1, 4,6}, {3, 6,8}, {2, 7,9}});
    return 0;
}*/

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:42:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |     for(auto [x,i]:V)
      |              ^

• 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