Submission #813836

#	Time	Username	Problem	Language	Result	Execution time	Memory
813836		KoD	메기 농장 (IOI22_fish)	C++17	100 / 100	137 ms	23684 KiB

fish

#include "fish.h"

#include <algorithm>
#include <array>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

using std::cerr;
using std::cin;
using std::cout;
using std::endl;

using std::array;
using std::pair;
using std::string;
using std::tuple;
using std::vector;

using std::begin;
using std::end;

using ll = long long;
constexpr int inf = (1 << 30) - 1;
constexpr ll infll = (1ll << 62) - 1;

template <class T> bool setmax(T& x, const T& y) { return x < y && (x = y, true); }

ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) { 
  vector<vector<array<int, 2>>> fish(N);
  for (int i = 0; i < M; ++i) {
    fish[X[i]].push_back({Y[i], W[i]});
  }
  for (auto& v : fish) {
    std::sort(begin(v), end(v));
    v.push_back({N, 0});
  }
  vector<ll> dp0(fish[0].size()), dp1(fish[0].size());
  for (int row = 1; row < N; ++row) {
    const int n = fish[row - 1].size();
    const int m = fish[row].size();
    vector<ll> ndp0(m), ndp1(m, *std::max_element(begin(dp0), end(dp0)));
    {
      vector<ll> acc(m);
      for (int i = 0; i < m - 1; ++i) {
        acc[i + 1] = acc[i] + fish[row][i][1];
      }
      int j = n;
      ll max = -infll;
      for (int i = m - 2; i >= 0; --i) {
        while (j > 0 && fish[row - 1][j - 1][0] > fish[row][i][0]) {
          j -= 1;
          setmax(max, dp0[j] + acc[i + 1]);
        }
        setmax(ndp0[i], max - acc[i]);
      }
    }
    {
      vector<ll> acc(n);
      for (int i = 0; i < n - 1; ++i) {
        acc[i + 1] = acc[i] + fish[row - 1][i][1];
      }
      int j = 0;
      ll max = -infll;
      for (int i = 0; i < m; ++i) {
        while (j < n && fish[row - 1][j][0] < fish[row][i][0]) {
          setmax(max, dp1[j] - acc[j]);
          j += 1;
        }
        setmax(ndp1[i], max + acc[j]);
      }
    }
    dp0 = std::move(ndp0);
    dp1 = std::move(ndp1);
    for (int i = 0; i < m; ++i) {
      setmax(dp0[i], dp1[i]);
    }
  }
  return *std::max_element(begin(dp0), end(dp0));
}

• 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