Submission #641996

#	Time	Username	Problem	Language	Result	Execution time	Memory
641996		Vanilla	Catfish Farm (IOI22_fish)	C++17	100 / 100	564 ms	132596 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
const int maxn = 2e5 + 2;
map <int64, int64> dp [maxn][2];
int64 mx [maxn];
vector <pair <int64, int64> > p[maxn];
vector <pair <int64, int64> > pref [maxn], suff[maxn];
vector <int64> pos [maxn];

int64 psum (int64 i, int64 j) {
  auto it = lower_bound(p[i].begin(), p[i].end(), make_pair(j, (int64) 1e18));
  if (it == p[i].begin()) return 0;
  return (--it)->second;
}

int64 max_weights(int n, int m, vector<int> x, vector<int> y,
                      vector<int> w) {
  for (int i = 0; i < m; i++) {
    pos[++x[i]].push_back(++y[i]);
    p[x[i]].push_back({y[i], w[i]});
  }
  for (int i = 1; i <= n; i++){
    sort(p[i].begin(), p[i].end());
    sort(pos[i].begin(), pos[i].end());
    int64 sum = 0;
    for (auto& [j, c]: p[i]) {
      int64 t = sum;
      sum+=c;
      c+=t;
      // cout << i << " " << j << " " << c << "\n";
    }
  }
  // cout << "> " << psum(1, 3) << " " << psum(1, 5) << " " << psum(1, 2) << "\n";
  for (int i = 1; i <= n; i++){
    vector <int64> ps = {0, n};
    for (auto j: pos[i-1]) ps.push_back(j);
    for (auto j: pos[i+1]) ps.push_back(j);
    sort(ps.begin(), ps.end());
    for (auto j: ps){
      auto it = lower_bound(suff[i-1].begin(), suff[i-1].end(), make_pair(j, -1ll));
      dp[i][j][0] = -psum(i, j);
      if (it != suff[i-1].end()) dp[i][j][0] += it->second;

      // dp[i][j][0] = suff[i-1][j] - p[i][j];

      it = lower_bound(pref[i - 1].begin(), pref[i - 1].end(), make_pair(j, (int64) 1e18));
      dp[i][j][1] = ((i - 2 >= 0) ? mx[i-2]: 0) + psum(i-1, j);
      if (it != pref[i-1].begin()) dp[i][j][1] = max(dp[i][j][1], (--it)->second + psum(i-1, j));
      // dp[i][j][1] = max(mx[i-2] + p[i-1][j], pref[i-1][j] + p[i-1][j]);


      mx[i] = max({mx[i], dp[i][j][0], dp[i][j][1]});
    }
    for (auto j: ps) {
      pref[i].push_back(make_pair(j, max((pref[i].empty() ? 0ll: pref[i].back().second), dp[i][j][1] - psum(i, j))));
    }
    reverse(ps.begin(), ps.end());
    for (auto j: ps) {
      suff[i].push_back(make_pair(j, max((suff[i].empty() ? 0ll: suff[i].back().second), max(dp[i][j][0], dp[i][j][1]) + psum(i + 1, j))));
    }
    reverse(suff[i].begin(), suff[i].end());
    // for (auto [j, c]: suff[i]) {
    //   cout << i << " " << j << " " << c << "\n";
    // }
    // for (int j = 0; j <= n; j++){
    //   pref[i][j] = max((j != 0 ? pref[i][j - 1]: 0ll), dp[i][j][1] - p[i][j]);
    // }
    // for (int j = n; j >= 0; j--){
    //   suff[i][j] = max((j != n ? suff[i][j + 1] : 0ll), max(dp[i][j][0], dp[i][j][1]) + p[i + 1][j]);
    // }
  }
  return mx[n];
}

• 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