Submission #1105494

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105494		VinhLuu	Catfish Farm (IOI22_fish)	C++17	100 / 100	382 ms	136712 KiB

fish

#include <bits/stdc++.h>
#define ll long long
#include "fish.h"
//#define all(lpv) lpv.begin(), lpv.end()
using namespace std;

const int N = 3e5 + 5;
const ll oo = -1e16;

int n, m;

void vin(ll &x,ll y){
  x = max(x, y);
}

vector<ll> a[N], b[N], f[3][N], g[3][N];

long long max_weights(int _N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
  n = _N;

  m = M;
  for(int i = 0; i <= n + 1; i ++){
    b[i].push_back(0);
    b[i].push_back(n + 1);
  }
  for(int i = 1; i <= m; i ++){
    int x = X[i - 1] + 1, y = Y[i - 1] + 1, c = W[i - 1];
    b[x].push_back(y);
    b[x - 1].push_back(y);
    b[x + 1].push_back(y);
  }
  for(int i = 0; i <= n + 1; i ++){
    sort(b[i].begin(), b[i].end());
    b[i].resize(unique(b[i].begin(), b[i].end()) - b[i].begin());
    int cnt = (int)(b[i].size());
    a[i].resize(cnt + 1);
    for(int k = 0; k <= 1; k ++){
      f[k][i].resize(cnt + 1);
      g[k][i].resize(cnt + 1);
    }
    for(int k = 0; k <= 1; k ++) for(int j = 0; j < a[i].size(); j ++){
      a[i][j] = 0;
      f[k][i][j] = oo;
      g[k][i][j] = oo;
    }
  }
  for(int i = 1; i <= m; i ++){
    int x = X[i - 1] + 1, y = Y[i - 1] + 1, c = W[i - 1];
    int u = lower_bound(b[x].begin(), b[x].end(), y) - b[x].begin();
    a[x][u] += c;
  }

  for(int i = 0; i <= n; i ++){
    for(int j = 1; j < b[i].size(); j ++) a[i][j] += a[i][j - 1];
  }

  f[0][0][0] = f[1][0][0] = 0;
  for(int i = 0; i < b[0].size(); i ++) g[1][0][i] = 0;

  ll ans = 0;

  for(int i = 1; i <= n; i ++){
    ll ret = oo;
    for(int j = 0; j < b[i - 1].size(); j ++) ret = max({ret, f[0][i - 1][j], f[1][i - 1][j]});
    f[0][i][0] = f[1][i][0] = ret;
    for(int j = 0; j < b[i].size(); j ++){
      int val = b[i][j];
      vin(f[1][i][j], 0);
      vin(f[0][i][j], 0);
      int pos = upper_bound(b[i - 1].begin(), b[i - 1].end(), val) - b[i - 1].begin() - 1;
      int tmp = lower_bound(b[i - 1].begin(), b[i - 1].end(), val) - b[i - 1].begin() - 1;
      if(tmp >= 0 && pos >= 0 && j > 0) vin(f[1][i][j], a[i - 1][pos] + g[1][i - 1][tmp]);
      tmp = upper_bound(b[i - 1].begin(), b[i - 1].end(), val) - b[i - 1].begin();
      vin(f[0][i][j], g[0][i - 1][tmp] - a[i][j]);
      vin(ans, max(f[1][i][j], f[0][i][j]));
    }

    for(int j = 0; j < b[i].size(); j ++){
      g[1][i][j] = f[1][i][j] - a[i][j];
      if(j > 0) vin(g[1][i][j], g[1][i][j - 1]);
    }
    for(int j = b[i].size() - 1; j >= 0; j --){
      int pos = upper_bound(b[i + 1].begin(), b[i + 1].end(), b[i][j]) - b[i + 1].begin() - 1;
      g[0][i][j] = max(f[0][i][j], f[1][i][j]) + a[i + 1][pos];
      if(j < b[i].size() - 1) vin(g[0][i][j], g[0][i][j + 1]);
    }
  }

  return ans;
}

//#define LOCAL

#ifdef LOCAL

int main() {

  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")){
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }
  int _N, M;
  assert(2 == scanf("%d %d", &_N, &M));

  std::vector<int> X(M), Y(M), W(M);
  for (int i = 0; i < M; ++i) {
    assert(3 == scanf("%d %d %d", &X[i], &Y[i], &W[i]));
  }

  long long result = max_weights(_N, M, X, Y, W);
  printf("%lld\n", result);
  return 0;
}

/*
5 4
0 2 5
1 1 2
4 4 1
3 3 3
*/

#endif // LOCAL

Compilation message (stderr)

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:27:45: warning: unused variable 'c' [-Wunused-variable]
   27 |     int x = X[i - 1] + 1, y = Y[i - 1] + 1, c = W[i - 1];
      |                                             ^
fish.cpp:41:51: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int k = 0; k <= 1; k ++) for(int j = 0; j < a[i].size(); j ++){
      |                                                 ~~^~~~~~~~~~~~~
fish.cpp:54:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int j = 1; j < b[i].size(); j ++) a[i][j] += a[i][j - 1];
      |                    ~~^~~~~~~~~~~~~
fish.cpp:58:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for(int i = 0; i < b[0].size(); i ++) g[1][0][i] = 0;
      |                  ~~^~~~~~~~~~~~~
fish.cpp:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int j = 0; j < b[i - 1].size(); j ++) ret = max({ret, f[0][i - 1][j], f[1][i - 1][j]});
      |                    ~~^~~~~~~~~~~~~~~~~
fish.cpp:66:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(int j = 0; j < b[i].size(); j ++){
      |                    ~~^~~~~~~~~~~~~
fish.cpp:78:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(int j = 0; j < b[i].size(); j ++){
      |                    ~~^~~~~~~~~~~~~
fish.cpp:85:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |       if(j < b[i].size() - 1) vin(g[0][i][j], g[0][i][j + 1]);
      |          ~~^~~~~~~~~~~~~~~~~

• 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