Submission #1244981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244981		pcp	Catfish Farm (IOI22_fish)	C++20	0 / 100	364 ms	357724 KiB

fish

#include "fish.h"
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#define ll long long

using namespace std;

const int NN=3005;

ll catfish[NN][NN];
ll pf[NN+1][NN+1];
vector<ll> memo[NN][NN];
int maxclaimed[NN];

int PN;



vector<ll> dp(int i, int h){
  //cout<<i<<" "<<h<<endl;
  vector<ll> e={-1,-1,-1};
  if (i>=PN)return {0,-1,-1};
  if (memo[i][h].size()>0)return memo[i][h];
  

  ll maxf=0;

  int saving=0;
  ll grandpa=0;

  for (int y = 0;y<=PN;++y){

    ll rslt = dp(i+1,y)[0];
    ll claimednext=dp(i+1,y)[1];
    
    
    //cout<<"Index: "<<i<<" | BF : "<<h<<" | H: "<<y<<" | MAXF: "<<claimednext<<endl;
    //cout<<rslt<<endl;
    if (i!=0 && y>h){
      rslt+=(pf[i-1][y] - pf[i-1][h]);
    }
    //cout<<rslt<<endl;

    ///

    if (dp(i+1,y)[2]<y && i<PN-1)rslt-=(pf[i][y] -  pf[i][dp(i+1,y)[2]]);
    else if (dp(i+1,y)[2]<y)rslt-=pf[i][y];

    //cout<<rslt<<" "<<dp(i+1,y)[2]<<endl;

    if (claimednext<y)rslt+=pf[i+1][y];
    else if (y>claimednext)rslt+=((pf[i+1][y] - pf[i+1][claimednext]));
    
    //cout<<rslt<<endl;

    //rslt-=pf[i][min(maxclaimed[i]+1,y+1)];
    //rslt+=pf[i+1][y];
    
    

    //cout<<rslt<<endl;

    //rslt-=pf[i][y];

    

    if (rslt>maxf){
      maxf=rslt;
      saving=y;
      grandpa=dp(i+1,y)[2];
      //maxclaimed[i-1]=saving;
    }


  }

  return memo[i][h]={maxf,grandpa,saving};

}


long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,std::vector<int> W) {
  memset(memo, {}, sizeof memo);
  memset(maxclaimed, -1, sizeof maxclaimed);
  memset(pf, 0, sizeof pf);
  memset(catfish, 0, sizeof catfish);
  //cout<<"2hola"<<endl;
  
  PN=N;

  for (int i = 0; i < M;++i)catfish[X[i]][Y[i]]=W[i];
  //cout<<"ho1la"<<endl;
  for (int x = 0; x < N+1;++x){
    ll c=0;
    pf[x][0]=0;
    for (int y =0;y<N+1;++y){
      c+=catfish[x][y];
      pf[x][y+1]=c;
    }
  }

  //cout<<"hola"<<endl;
 
  return dp(0,0)[0];
}

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