Submission #798611

#	Time	Username	Problem	Language	Result	Execution time	Memory
798611		oscar1f	Catfish Farm (IOI22_fish)	C++17	12 / 100	170 ms	59444 KiB

fish

#include "fish.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long

const ll MAX_TAILLE=100*1000+5,MAX_BON=500*1000+5,INFINI=(ll)1000*1000*1000*1000*1000*10;
ll taille,nbBonus;
ll posBon[MAX_BON][2];
vector<tuple<ll,ll,ll>> bonSurCol[MAX_TAILLE];
ll memo[MAX_BON][2];

ll premSous(ll col,ll lig) {
    ll deb=0,mid,fin=bonSurCol[col].size()-1;
    while (deb!=fin) {
        mid=(deb+fin+1)/2;
        if (get<0>(bonSurCol[col][mid])<=lig) {
            deb=mid;
        }
        else {
            fin=mid-1;
        }
    }
    return get<2>(bonSurCol[col][deb]);
}

ll premSur(ll col,ll lig) {
    ll deb=0,mid,fin=bonSurCol[col].size()-1;
    while (deb!=fin) {
        mid=(deb+fin)/2;
        if (get<0>(bonSurCol[col][mid])>=lig) {
            fin=mid;
        }
        else {
            deb=mid+1;
        }
    }
    return get<2>(bonSurCol[col][deb]);
}

ll dyna(ll idReq,ll desc) {
    if (memo[idReq][desc]!=-1) {
        return memo[idReq][desc];
    } 
    ll col=posBon[idReq][0],num=posBon[idReq][1];
    ll valBon=get<1>(bonSurCol[col][num]);
    //cout<<idReq<<" : "<<premSous(col+1,get<0>(bonSurCol[col][num]))<<" "<<premSur(col+1,get<0>(bonSurCol[col][num]))<<endl;
    //return 42;
    if (desc==0) {
        if (num==0) {
            memo[idReq][desc]=max(dyna(idReq+2,1),dyna(idReq+5,0));
        }
        else if (num==(ll)bonSurCol[col].size()-1) {
            memo[idReq][desc]=max(dyna(get<2>(bonSurCol[col][num-1]),0),dyna(premSous(col+1,get<0>(bonSurCol[col][num])),0));
        }
        else {
            memo[idReq][desc]=max(dyna(get<2>(bonSurCol[col][num-1]),0),dyna(premSous(col+1,get<0>(bonSurCol[col][num])-1),0));
        }
    }
    else {
        if (num==(ll)bonSurCol[col].size()-1) {
            memo[idReq][desc]=dyna(idReq+4,0);
        }
        else if (num==0) {
            memo[idReq][desc]=max(dyna(get<2>(bonSurCol[col][num+1]),1),dyna(premSur(col+1,get<0>(bonSurCol[col][num])),1));
        }
        else {
            memo[idReq][desc]=max(dyna(get<2>(bonSurCol[col][num+1]),1),dyna(premSur(col+1,get<0>(bonSurCol[col][num])+1),1));
        }
    }
    memo[idReq][desc]+=valBon;
    return memo[idReq][desc];
}

ll max_weights(int N,int M,vector<int> X,vector<int> Y,vector<int> W) {
    taille=N;
    nbBonus=M+2*(N+1);
    for (ll i=0;i<M;i++) {
        bonSurCol[X[i]].push_back(make_tuple(Y[i],W[i],i));
    }
    for (ll i=0;i<=taille;i++) {
        bonSurCol[i].push_back(make_tuple(-1,0,M+2*i));
        bonSurCol[i].push_back(make_tuple(taille+1,0,M+2*i+1));
        sort(bonSurCol[i].begin(),bonSurCol[i].end());
        //cout<<i<<" : "; 
        for (ll j=0;j<(ll)bonSurCol[i].size();j++) {
            //cout<<get<0>(bonSurCol[i][j])<<" "<<get<1>(bonSurCol[i][j])<<" "<<get<2>(bonSurCol[i][j])<<"     ";
            posBon[get<2>(bonSurCol[i][j])][0]=i;
            posBon[get<2>(bonSurCol[i][j])][1]=j;
        }
        //cout<<endl;
    }
    for (ll i=0;i<nbBonus-2;i++) {
        memo[i][0]=-1;
        memo[i][1]=-1;
    }
    for (auto k:bonSurCol[taille-1]) {
        memo[get<2>(k)][1]=-INFINI;
    }
    ll temp=dyna(M,1);
    /*for (ll i=0;i<nbBonus;i++) {
        for (ll j=0;j<3;j++) {
            cout<<i<<" "<<j<<" : "<<dyna(i,j)<<endl;
        }
    }*/
    return temp;
}

• Subtask 1: 3 / 3
• Subtask 2: 0 / 6
• Subtask 3: 9 / 9
• Subtask 4: 0 / 14
• Subtask 5: 0 / 21
• Subtask 6: 0 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16