Submission #629225

#	Time	Username	Problem	Language	Result	Execution time	Memory
629225		kdh9949	Catfish Farm (IOI22_fish)	C++17	100 / 100	523 ms	38252 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;

using vint = vector<int>;
using vll = vector<ll>;
using vld = vector<ld>;
using vpii = vector<pii>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vpll = vector<pll>;

#define x first
#define y second
#define all(v) (v).begin(),(v).end()

const int SZ = 131072;
const ll INF = ll(1e18);
struct Seg {
  ll d[2 * SZ];
  void u(int x, ll v) {
    for(x += SZ; x; x /= 2) d[x] = max(d[x], v);
  }
  ll g(int s = 0, int e = SZ - 1) {
    ll r = 0;
    for(s += SZ, e += SZ; s <= e; s /= 2, e /= 2) {
      if(s & 1) r = max(r, d[s++]);
      if(~e& 1) r = max(r, d[e--]);
    }
    return r;
  }
} U[3], D[3];

ll max_weights(int N, int M, vint X, vint Y, vint W) {
  vector<vpil> a(N);
  vector<vpll> d(N);
  for(int i = 0; i < M; i++) {
    a[X[i]].emplace_back(Y[i], W[i]);
    d[X[i]].emplace_back(-INF, -INF);
  }
  for(int i = 0; i < N; i++) sort(all(a[i]));

  for(int i = 0; i < N; i++) {
    for(int j = 1; j <= 2; j++) if(i - j >= 0)
      for(int k = 0; k < a[i - j].size(); k++) {
        U[j].u(a[i - j][k].x, d[i - j][k].x);
        D[j].u(a[i - j][k].x, d[i - j][k].y);
      }
    int K = a[i].size();
    if(i < N - 1) for(int j = 0; j < K; j++) {
      d[i][j].x = max(U[0].g(0, a[i][j].x - 1), D[1].g()) + a[i][j].y;
      U[0].u(a[i][j].x, d[i][j].x);
    }
    if(i) for(int j = K - 1; j >= 0; j--) {
      d[i][j].y = max({D[0].g(a[i][j].x + 1), U[2].g(), D[2].g()}) + a[i][j].y;
      D[0].u(a[i][j].x, d[i][j].y);
    }
  }

  ll ans = 0;
  for(auto &v : d) for(auto &p : v) ans = max({ans, p.x, p.y});
  return ans;
}

Compilation message (stderr)

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

• 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