Submission #1125912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125912		zNatsumi	Catfish Farm (IOI22_fish)	C++20	100 / 100	161 ms	51284 KiB

fish

#include <bits/stdc++.h>

using namespace std;

using ii = pair<int, int>;
const int32_t N = 1e5 + 5,
              M = 3e5 + 5;
const int64_t INF = 1e18;

int n, m;
struct info{
  int x, y, w;
  info(){}
  info(int x, int y, int w): x(x), y(y), w(w) {}
} fish[M];

namespace AC{
  vector<ii> fish_in_col[N];
  vector<long long> pref[2][N], dp[2][N];
  long long _max[N];

  void init(){
    for(int i = 1; i <= m; i++) fish_in_col[fish[i].x].emplace_back(fish[i].y, fish[i].w);
    for(int i = 1; i <= n; i++){
      fish_in_col[i].emplace_back(0, 0);
      sort(fish_in_col[i].begin(), fish_in_col[i].end());

      for(auto x : {0, 1}) dp[x][i].resize(fish_in_col[i].size() + 1, 0);
      //
      _max[i] = -INF;
      pref[1][i].resize(fish_in_col[i].size() + 1, (i > 1 ? -INF : 0)); pref[1][i][0] = 0;
      pref[0][i].resize(fish_in_col[i].size() + 1, (i > 1 ? -INF : 0)); pref[0][i][0] = 0;
    }
  }

  long long solve(){
    init();

    long long res = 0;
    for(int i = 1; i <= n; i++){
      dp[0][i][0] = max(i > 1 ? pref[0][i - 1][0] : 0, _max[i - 1]);
      dp[1][i][0] = max(i > 1 ? pref[0][i - 1][0] : 0, _max[i - 1]);
      if(i > 1){
        long long add = 0, sub = 0;

        for(int j = 1, pj = 0; j < fish_in_col[i].size(); j++){
          auto [y, w] = fish_in_col[i][j];
          add += 1LL * w;
          while(pj < fish_in_col[i - 1].size() - 1 && fish_in_col[i - 1][pj + 1].first <= fish_in_col[i][j].first) sub += fish_in_col[i - 1][++pj].second;
          auto tmp = (fish_in_col[i - 1][pj].first < fish_in_col[i][j].first);
          dp[0][i][j] = max(dp[0][i][j], pref[0][i - 1][pj + tmp] + add - sub);
        }
        dp[0][i][fish_in_col[i].size() - 1] = max(dp[0][i][fish_in_col[i].size() - 1], add);
        for(int j = 0; j < fish_in_col[i - 2].size(); j++) dp[0][i][fish_in_col[i].size()-1] = max({dp[0][i][fish_in_col[i].size()-1], dp[0][i - 2][j] + add, dp[1][i - 2][j] + add});
      }

      if(i < n){
        long long add = 0;
        for(int j = 1; j < fish_in_col[i].size(); j++){
          auto [y, w] = fish_in_col[i][j];
          add += w;
          dp[1][i][j] = max(dp[1][i][j], pref[1][i][j] + add);
          dp[1][i][j] = max(dp[1][i][j], (i > 1 ? pref[0][i - 1][0] : 0) + add);
          if(i > 1) dp[1][i][j] = max(dp[1][i][j], _max[i - 2]);
          res = max(res, dp[1][i][j]);
        }
      }
      for(int j = fish_in_col[i].size() - 1; j >= 0; j--){
        pref[0][i][j] = max(dp[0][i][j], pref[0][i][j + 1]);
        _max[i] = max(_max[i], dp[1][i][j]);
      }

      long long add = 0;
      for(int j = 1, pj = 0; j < fish_in_col[i + 1].size(); j++){
        auto [y, w] = fish_in_col[i + 1][j];
        while(pj < fish_in_col[i].size() - 1 && fish_in_col[i][pj + 1].first < fish_in_col[i + 1][j].first) pj += 1;

        pref[1][i + 1][j] = max(pref[1][i + 1][j - 1], dp[1][i][pj] - add);
        add += w;
      }
      res = max(res, pref[0][i][0]);
    }
    return res;
  }
}

int64_t max_weights(int _N, int _M, vector<int> _X, vector<int> _Y, vector<int> _W){
  n = _N; m = _M;
  for(int i = 0; i < m; i++) fish[i + 1] = info(_X[i] + 1, _Y[i] + 1, _W[i]);

  bool flag1 = true;
  for(int i = 1; i <= m; i++) if(!(fish[i].x & 1)){ flag1 = false; break; }

  return AC::solve();
}

//#define zNatsumi
#ifdef zNatsumi

int main(){
  cin.tie(0)->sync_with_stdio(0);
  #define task "test"
  if(fopen(task ".inp", "r")){
    freopen(task ".inp", "r", stdin);
    freopen(task ".out", "w", stdout);
  }
  int n, m; cin >> n >> m;
  vector<int> x(m), y(m), w(m);
  for(int i = 0; i < m; i++) cin >> x[i] >> y[i] >> w[i];

  cout << max_weights(n, m, x, y, w);
}
/*
5 4
0 2 5
1 1 2
4 4 1
3 3 3
*/
#endif

• 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