Submission #635095

#	Time	Username	Problem	Language	Result	Execution time	Memory
635095		ruhanhabib39	Catfish Farm (IOI22_fish)	C++17	53 / 100	1161 ms	1976680 KiB

fish

#include "fish.h"

#include <vector>
#include <array>
#include <iostream>

namespace ruhan {
   using namespace std;

   int N, M;

   int H;
   vector<vector<long long>> ss;
   vector<vector<array<long long, 2>>> dp;

   vector<int> X, Y, W;

   bool is_subtask1;
   bool is_subtask2;

   void init (int N_, int M_, vector<int> X_, vector<int> Y_, vector<int> W_) {
      N = N_;
      M = M_;
      X = X_;
      Y = Y_;
      W = W_;

      H = 0;
      for (int i = 0; i < M; i++) {
         H = max(H, Y[i]);
      }
      H++;

      is_subtask1 = true;
      for (int i = 0; i < M; i++) {
         is_subtask1 = is_subtask1 && (X[i] % 2 == 0);
      }

      is_subtask2 = true;
      for (int i = 0; i < M; i++) {
         is_subtask2 = is_subtask2 && X[i] <= 1;
      }

      if (is_subtask1) return;

      if (is_subtask2) {
         ss = vector<vector<long long>>(2, vector<long long>(H, 0LL));
      } else {
         ss = vector<vector<long long>>(N, vector<long long>(H, 0LL));
         dp = vector<vector<array<long long, 2>>>(N + 1, vector<array<long long, 2>>(H + 1));
      }

      for (int i = 0; i < M; i++) {
         ss[X[i]][Y[i]] += W[i];
      }

      for (int x = 0; x < (int)ss.size(); x++) {
         for (int y = 1; y < H; y++) {
            ss[x][y] += ss[x][y-1];
         }
      }
   }

   long long get_sum (int x, int ly, int ry) {
      ly = max(0, ly);
      ry = min(H - 1, ry);

      if (x < 0 || x >= N || ry < ly) return 0;
      if (ly == 0) return ss[x][ry];
      return ss[x][ry] - ss[x][ly-1];
   }

   long long subtask345 () {
      //fill(dp[N].begin(), dp[N].end(), 0LL);
      for (int x = N - 1; x >= 0; x--) {
         for (int h = 0; h <= H; h++) {
            for (int s : {0, 1}) {
               const int H1 = s ? h : H;
               for (int y = 0; y <= H1; y++) {
                  long long val = get_sum(x-1,h,y-1) + get_sum(x+1,0,y-1);

                  val -= get_sum(x, 0, min(h-1,y-1));
                  val += dp[x+1][y][y < h];

                  if (x == 4 && h == 0 && s == 1) {
                     //cerr << "left adding " << get_sum(x-1,h,y-1) << "\n";
                     //cerr << "right adding " << get_sum(x+1,0,y-1) << "\n";
                     //cerr << "mid removing " << get_sum(x, 0, min(h-1,y-1)) << "\n";
                     //cerr << "val(" << y << ") = " << val << "\n";
                  }
                  dp[x][h][s] = max(dp[x][h][s], val);
               }

               if (x < N - 1) {
                  for (int y = 0; y <= H; y++) {
                     long long val = get_sum(x, h, y-1);

                     if (x == 4 && h == 0 && s == 1) {
                        //cerr << "for y = " << y << ", middle adding " << get_sum(x, h, y-1) << "\n";
                     }

                     val += get_sum(x+2, 0, y - 1);
                     val += x + 2 <= N ? dp[x+2][y][0] : 0;
                     dp[x][h][s] = max(dp[x][h][s], val);
                  }

                  if (x == 4 && h == 0 && s == 1) {
                     //cerr << "dp -> " << dp[x][h][s] << "\n";
                  }
               }
            }
         }
      }

      return dp[0][0][0];
   }

   long long subtask1 () {
      long long res = 0;
      for (int i = 0; i < M; i++) {
         res += W[i];
      }
      return res;
   }

   long long subtask2 () {
      long long res = max(get_sum(0, 0,  H - 1), get_sum(1, 0, H - 1));

      if (N > 2) {
         for (int y = 0; y <= H; y++) {
            long long val = get_sum(0, 0, y - 1) + get_sum(1, y, H - 1);
            res = max(res, val);
         }
      }

      return res;
   }

   long long calc () {
      if (is_subtask1) return subtask1();
      if (is_subtask2) return subtask2();
      return subtask345();
   }
};

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
   ruhan::init(N, M, X, Y, W);
   return ruhan::calc();
}

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