Submission #828167

#	Time	Username	Problem	Language	Result	Execution time	Memory
828167		Amylopectin	Catfish Farm (IOI22_fish)	C++17	100 / 100	290 ms	93864 KiB

fish

#include "fish.h"
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const long long mxn = 1e6 + 10;
struct we
{
  long long hei,wei;
};
struct sdp
{
  long long al,alnr,lowe,acal,acalnr,aclowe;
};
bool cmp(const struct we &l,const struct we &r)
{
  return l.hei < r.hei;
}
vector<struct sdp> dp[mxn] = {}; 
vector<struct we> fil[mxn] = {};
long long n,m;
long long max_weights(int N, int M, std::vector<int> cc
, std::vector<int> rr,std::vector<int> ww) 
{
  long long i,j,cn,cm,fn,fm,rul,rur,vce,val,var,rul2;
  n = N;
  m = M;
  for(i=0; i<m; i++)
  {
    dp[cc[i]].push_back({0,0,0,0,0,0});
    fil[cc[i]].push_back({rr[i],ww[i]});
  }
  for(i=0; i<n; i++)
  {
    fil[i].push_back({n+2,0});
    dp[i].push_back({0,0,0,0,0,0});
    // fil[i].push_back({-1,0});
    // dp[cc[i]].push_back({0,0,0,0,0,0});
    sort(fil[i].begin(),fil[i].end(),cmp);
  }
  for(i=0; i<n; i++)
  {
    rul = 0;
    rur = 0;
    vce = 0;
    val = 0;
    var = 0;
    rul2 = 0;
    for(j=0; j<fil[i].size(); j++)
    {
      if(i > 0)
        while(fil[i-1][rul].hei < fil[i][j].hei)
        {
          val += fil[i-1][rul].wei;
          rul ++;
        }
      if(i>1)
        while(fil[i-2][rul2].hei < fil[i][j].hei)
        {
          rul2 ++;
        }
      while(i<n-1 && fil[i+1][rur].hei < fil[i][j].hei)
      {
        var += fil[i+1][rur].wei;
        rur ++;
      }
      if(rul2 > 0 && i>1)
      {
        dp[i][j].lowe = dp[i-2][rul2-1].acalnr + val;
        // dp[i][j].alnr = dp[i-2][rul2-1].acalnr + val;
      }
      if(i>1)
        dp[i][j].lowe = max(dp[i][j].lowe,dp[i-2][dp[i-2].size()-1].acal);
      // dp[i][j].alnr = max(dp[i][j].alnr,dp[i-2][dp[i-2].size()-1].acal);
      if(rul > 0 && i>0)
      {
        dp[i][j].lowe = max(dp[i][j].lowe,dp[i-1][rul-1].aclowe + val);
      }
      if(i>0)
        dp[i][j].alnr = max(dp[i][j].lowe,dp[i-1][dp[i-1].size()-1].acal - vce);
      dp[i][j].al = dp[i][j].alnr + var;
      if(j > 0)
      {
        dp[i][j].acal = max(dp[i][j].al,dp[i][j-1].acal);
        dp[i][j].acalnr = max(dp[i][j].alnr,dp[i][j-1].acalnr);
        dp[i][j].aclowe = max(dp[i][j].lowe - vce,dp[i][j-1].aclowe);
      }
      else 
      {
        dp[i][j].acal = dp[i][j].al;
        dp[i][j].acalnr = dp[i][j].alnr;
        dp[i][j].aclowe = dp[i][j].lowe - vce;
      }
      vce += fil[i][j].wei;
    }
  }
  return dp[n-1][dp[n-1].size()-1].acalnr;
}

Compilation message (stderr)

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:50:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<we>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(j=0; j<fil[i].size(); j++)
      |              ~^~~~~~~~~~~~~~
fish.cpp:26:17: warning: unused variable 'cn' [-Wunused-variable]
   26 |   long long i,j,cn,cm,fn,fm,rul,rur,vce,val,var,rul2;
      |                 ^~
fish.cpp:26:20: warning: unused variable 'cm' [-Wunused-variable]
   26 |   long long i,j,cn,cm,fn,fm,rul,rur,vce,val,var,rul2;
      |                    ^~
fish.cpp:26:23: warning: unused variable 'fn' [-Wunused-variable]
   26 |   long long i,j,cn,cm,fn,fm,rul,rur,vce,val,var,rul2;
      |                       ^~
fish.cpp:26:26: warning: unused variable 'fm' [-Wunused-variable]
   26 |   long long i,j,cn,cm,fn,fm,rul,rur,vce,val,var,rul2;
      |                          ^~

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