Submission #635920

#	Time	Username	Problem	Language	Result	Execution time	Memory
635920		slime	Catfish Farm (IOI22_fish)	C++17	100 / 100	453 ms	94100 KiB

fish

#include "fish.h"
#include "bits/stdc++.h"


#include <vector>

using namespace std;


vector<pair<int, long long> > cs[100010];

long long columnSum(int i, int R) {
  if(R < 0) return 0;
  if(cs[i].empty()) return 0;
  int lb = 0, rb = cs[i].size() - 1;
  while(lb < rb) {
    int mid = (lb + rb + 1) >> 1;
    if(cs[i][mid].first <= R) lb = mid;
    else rb = mid - 1;
  }
  if(cs[i][lb].first <= R) return cs[i][lb].second;
  else return 0;
}


vector<int> possible_heights[100010];


long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {

  for(int i=0; i<M; i++) {
    cs[X[i]].push_back({Y[i], W[i]});
    possible_heights[X[i]].push_back(Y[i]);
  }

  for(int i=0; i<N; i++) {
    possible_heights[i].push_back(0);
    possible_heights[i].push_back(N);
  }

  for(int i=0; i<N; i++) {
    sort(possible_heights[i].begin(), possible_heights[i].end());
  }

  for(int i=0; i<N; i++) sort(cs[i].begin(), cs[i].end());

  for(int i=0; i<N; i++) {
    for(int j=1; j<cs[i].size(); j++) {
      cs[i][j].second += cs[i][j-1].second;
    }
  }


  unordered_map<int, long long> DP[N][2];//0-> upwards, 1->downwards or plains

  for(int i=1; i<N; i++) {
    // State = 0: upwards (H[i-1] < H[i])
    {
      // H[i-1] > 0

      long long ptr = -1, qq = -5e14;
      for(int x: possible_heights[i]) {
        while(ptr + 1 < possible_heights[i-1].size() && possible_heights[i-1][ptr + 1] < x) {
          ptr++;
          int hh = possible_heights[i-1][ptr];
          if(hh > 0 || i == 1) qq = max(qq, DP[i-1][0][hh] - columnSum(i-1, hh-1)); // If i = 1, hh = 0 is ok
        }
        DP[i][0][x] = max(DP[i][0][x], qq + columnSum(i-1, x-1));
      }
      // H[i-1] = 0
      if(i > 1) {
        // y 0 x, y < x
        ptr = -1, qq = -5e14;
        for(int x: possible_heights[i]) {
          while(ptr + 1 < possible_heights[i-2].size() && possible_heights[i-2][ptr + 1] < x) {
            ptr++;
            int hh = possible_heights[i-2][ptr];
            long long vv = max(DP[i-2][0][hh], DP[i-2][1][hh]);
            qq = max(qq, vv);
          }
          DP[i][0][x] = max(DP[i][0][x], qq + columnSum(i-1, x-1));
        }
        // y 0 x, y >= x
        ptr = possible_heights[i-2].size(), qq = -5e14;
        reverse(possible_heights[i].begin(), possible_heights[i].end());
        for(int x: possible_heights[i]) {
          while(ptr - 1 >= 0 && possible_heights[i-2][ptr - 1] >= x) {
            ptr--;
            int hh = possible_heights[i-2][ptr];
            long long vv = max(DP[i-2][0][hh], DP[i-2][1][hh]);
            qq = max(qq, vv + columnSum(i-1, hh-1));
          }
          DP[i][0][x] = max(DP[i][0][x], qq);
        }
        reverse(possible_heights[i].begin(), possible_heights[i].end());
      }
    }
    // State = 1: downwards (H[i-1] >= H[i])
    {
      reverse(possible_heights[i].begin(), possible_heights[i].end());
      long long ptr = possible_heights[i-1].size(), qq = -5e14;
      for(int x: possible_heights[i]) {
        while(ptr - 1 >= 0 && possible_heights[i-1][ptr - 1] >= x) {
          ptr--;
          int hh = possible_heights[i-1][ptr];
          qq = max(qq, max(DP[i-1][0][hh], DP[i-1][1][hh]) + columnSum(i, hh-1));
        }
        DP[i][1][x] = max(DP[i][1][x], qq - columnSum(i, x-1));
      }
      reverse(possible_heights[i].begin(), possible_heights[i].end());
    }

    for(int x: possible_heights[i]) {
      DP[i][0][x] = max(DP[i][0][x], 0ll);
      DP[i][1][x] = max(DP[i][1][x], 0ll);
    }
  }

  long long ans = 0;
  for(int x: possible_heights[N-1]) ans = max(ans, max(DP[N-1][0][x], DP[N-1][1][x]));
  return ans;
}

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:48:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for(int j=1; j<cs[i].size(); j++) {
      |                  ~^~~~~~~~~~~~~
fish.cpp:63:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         while(ptr + 1 < possible_heights[i-1].size() && possible_heights[i-1][ptr + 1] < x) {
      |               ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:75:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |           while(ptr + 1 < possible_heights[i-2].size() && possible_heights[i-2][ptr + 1] < x) {
      |                 ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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