Submission #737700

#	Time	Username	Problem	Language	Result	Execution time	Memory
737700		iee	Catfish Farm (IOI22_fish)	C++17	100 / 100	601 ms	109148 KiB

fish

#include <bits/stdc++.h>
#include "fish.h"
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
map<int, ll> v[N], h[N];
vector<ll> f[N];
vector<int> pos[N];
vector<pair<int, ll>> S[N];
ll s(int p, int u) {
  if (auto it = lower_bound(S[p].begin(), S[p].end(), pair(u + 1, (ll) -1e18)); it != S[p].begin()) return prev(it)->second;
  return 0;
}
ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
  for (int i = 0; i < m; ++i)
    v[x[i] + 1][y[i] + 1] += w[i], pos[x[i] + 1].push_back(y[i]); 
  for (int i = 1; i <= n; ++i) {
    sort(pos[i].begin(), pos[i].end()), pos[i].push_back(n);
    ll c = 0;
    for (auto [p, v]: v[i])
      c += v, S[i].emplace_back(p, c);
  }
  for (int j: pos[1])
    h[1][j] = 0;
  f[1].resize(pos[1].size());
  for (int i = 2; i <= n; ++i) {
    f[i].resize(pos[i].size());
    auto g = pos[i - 1].size() - 1;
    ll ma = -1e18;
    for (int j = (int) pos[i].size() - 1; j >= 0; --j) {
      while (~g && pos[i - 1][g] >= pos[i][j])
        ma = max(ma, f[i - 1][g] + s(i, pos[i - 1][g])), --g;
      f[i][j] = ma - s(i, pos[i][j]);
    }
    auto l = h[i - 1].begin();
    ma = -1e18;
    for (int j = 0; j < pos[i].size(); ++j) {
      while (l != h[i - 1].end() && l->first <= pos[i][j])
        ma = max(ma, l->second - s(i - 1, l->first)), ++l;
      f[i][j] = max(f[i][j], h[i][pos[i][j]] = ma + s(i - 1, pos[i][j]));
    }
    for (int j = 0; j < pos[i - 1].size(); ++j)
      h[i][pos[i - 1][j]] = max(h[i][pos[i - 1][j]], f[i - 1][j] + s(i, pos[i - 1][j]));
  }
  ll mx = 0;
  for (ll v: f[n])
    mx = max(mx, v);
  return mx;
}

Compilation message (stderr)

fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (int j = 0; j < pos[i].size(); ++j) {
      |                     ~~^~~~~~~~~~~~~~~
fish.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int j = 0; j < pos[i - 1].size(); ++j)
      |                     ~~^~~~~~~~~~~~~~~~~~~

• 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