Submission #790957

#	Time	Username	Problem	Language	Result	Execution time	Memory
790957		alexander707070	Carnival Tickets (IOI20_tickets)	C++14	27 / 100	631 ms	176260 KiB

tickets

#include<bits/stdc++.h>
#include "tickets.h"
#define MAXN 1507
using namespace std;

const long long inf=1e15;

int n,m,sol[MAXN];
pair<int,int> mins[MAXN],maxs[MAXN];
set< pair<int,int> > s[MAXN];
pair<int,int> p;
vector<int> curr;
vector< vector<int> > res;

int li[MAXN][MAXN],tim;
long long dp[MAXN][MAXN],ans;

long long ff(int pos,int balance){
    if(balance>pos+1)return -inf;
    if(pos==-1)return 0;

    if(li[pos][balance]==tim)return dp[pos][balance];
    li[pos][balance]=tim;

    dp[pos][balance]=ff(pos-1,balance)+maxs[pos].first;
    if(balance>0){
        dp[pos][balance]=max(dp[pos][balance],ff(pos-1,balance-1)-mins[pos].first);
    }

    return dp[pos][balance];
}

void solve(int pos,int balance){
    if(pos==-1)return;

    if(ff(pos,balance)==ff(pos-1,balance)+maxs[pos].first){
        sol[pos]=1; solve(pos-1,balance);
        return;
    }else{
        sol[pos]=0; solve(pos-1,balance-1);
        return;
    }
}

long long find_maximum(int k,vector< vector<int> > x){
    n=int(x.size()); m=int(x[0].size());
    res.resize(n);

    for(int i=0;i<n;i++){
        res[i].resize(m);
        for(int f=0;f<m;f++){
            s[i].insert({x[i][f],f});
            res[i][f]=-1;
        }
    }

    for(int i=0;i<k;i++){
        for(int f=0;f<n;f++){
            mins[f]=*s[f].begin();
            maxs[f]=*s[f].rbegin();
        }

        tim++; solve(n-1,n/2);

        curr.clear();
        for(int f=0;f<n;f++){
            if(sol[f]==0){
                curr.push_back(mins[f].first);
                res[f][mins[f].second]=i;
                s[f].erase(s[f].find(mins[f]));
            }else{
                curr.push_back(maxs[f].first);
                res[f][maxs[f].second]=i;
                s[f].erase(s[f].find(maxs[f]));
            }
        }

        sort(curr.begin(),curr.end());

        for(int f=0;f<curr.size();f++){
            ans+=abs(curr[n/2]-curr[f]);
        }
    }

    allocate_tickets(res);
    return ans;
}


/*
int main(){
    cout<<find_maximum(2, {{0, 2, 5},{1, 1, 3}})<<"\n";
}
*/

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:80:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for(int f=0;f<curr.size();f++){
      |                     ~^~~~~~~~~~~~

• 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