제출 #1244994

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1244994		pcp	Catfish Farm (IOI22_fish)	C++20	0 / 100	288 ms	287024 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];

pair<ll,pair<int,int>> memo[NN][NN];

int PN;



pair<ll,pair<int,int>> dp(int i, int h){
  //cout<<i<<" "<<h<<endl;
  pair<ll,pair<int,int>> e={-1,{-1,-1}};
  if (i>=PN)return {0,{-1,-1}};
  if ( !(memo[i][h].first==-1 &&memo[i][h].second.second==-1&&memo[i][h].second.second==-1) )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).first;
    ll claimednext=dp(i+1,y).second.first;
    
    
    //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).second.second<y && i<PN-1)rslt-=(pf[i][y] -  pf[i][dp(i+1,y).second.second]);
    else if (dp(i+1,y).second.second<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).second.second;
      //maxclaimed[i-1]=saving;
    }


  }

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

}


ll max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,std::vector<int> W) {
  memset(pf, 0, sizeof pf);
  memset(catfish, 0, sizeof catfish);
  memset(memo, -1, sizeof memo);
  //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).first;
}

• 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