Submission #790986

#	Time	Username	Problem	Language	Result	Execution time	Memory
790986		alexander707070	Carnival Tickets (IOI20_tickets)	C++14	0 / 100	212 ms	44536 KiB

tickets

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

const long long inf=1e15;

int n,m,sol[MAXN],k,rest[MAXN],br;
long long pref[MAXN][MAXN],suff[MAXN][MAXN];
pair<int,int> mins[MAXN],maxs[MAXN];
pair<int,int> s[MAXN][MAXN];
vector<int> curr;
vector< vector<int> > res;

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

long long ff(int pos,int balance){
    if(balance<0)return -inf;
    if(pos==-1 and balance==0)return 0;
    else if(pos==-1)return -inf;

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

    for(int i=0;i<=k;i++){
        dp[pos][balance]=max(dp[pos][balance],ff(pos-1,balance-i)+suff[pos][k-i]-pref[pos][i]);
    }

    return dp[pos][balance];
}

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

    for(int i=0;i<=min(k,balance);i++){
        if(ff(pos,balance)==ff(pos-1,balance-i)+suff[pos][k-i]-pref[pos][i]){
            sol[pos]=i; rest[pos]=k-i;
            solve(pos-1,balance-i);
            return;
        }
    }
}

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

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

        for(int f=0;f<m;f++){
            pref[i][f+1]=s[i][f].first;
            pref[i][f+1]+=pref[i][f];
        }
        for(int f=m-1;f>=0;f--){
            suff[i][m-f]=s[i][f].first;
            suff[i][m-f]+=suff[i][m-f-1];
        }   
    }

    tim++; solve(n-1,(n/2)*k);
    ans=ff(n-1,(n/2)*k);

    for(int i=0;i<k;i++){
        br=n/2;

        for(int f=0;f<n;f++){
            if(sol[f]>0 and br>0){
                res[f][s[f][sol[f]-1].second]=i;
                sol[f]--; br--;
            }else{
                if(rest[f]==0)cout<<1/0;
                res[f][s[f][m-rest[f]].second]=i;
                rest[f]--;
            }
        }

        //if(br>0)cout<<1/0;
    }

    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:79:38: warning: division by zero [-Wdiv-by-zero]
   79 |                 if(rest[f]==0)cout<<1/0;
      |                                     ~^~

• Subtask 1: 0 / 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