Submission #1028098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028098		NeroZein	Catfish Farm (IOI22_fish)	C++17	78 / 100	1091 ms	63160 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
 
using namespace std;
 
int n; 
vector<vector<long long>> nxt;
vector<vector<long long>> pre;
vector<vector<pair<int, int>>> in_col;
vector<vector<vector<long long>>> dp;
 
long long bt(int col, bool f, bool f2) {//is last bigger and does he need payment if he is not
  if (col >= n) {
    return 0;
  }
  long long& ret = dp[col][f][f2];
  if (ret != -1) {
    return ret; 
  }
  ret = 0; 
  int sz = in_col[col].size();
  if (f) {//last is bigger, (he paid for me)
    long long s = 0; 
    for (int i = 0; i < sz; ++i) {
      long long w = s; 
      if (col < n - 1) {
        w += nxt[col][i]; 
      }
      ret = max(ret, bt(col + 1, 1, 0) + w); //I'm bigger than next
      s -= in_col[col][i].second;//delete what I covered 
    }
    //don't build anything..
    ret = max(ret, bt(col + 1, 0, 0));//telling next not to pay for me or take from me
  } else {//last is smaller, I pay for him if f2
    long long s = 0; 
    for (int i = 0; i < sz; ++i) {
      long long w = s;
      if (f2) {
        w += pre[col][i]; 
      }
      ret = max(ret, bt(col + 1, 0, 1) + w); //I'm smaller than next and I need payment (I'll subtract what I cover)
      s -= in_col[col][i].second; 
    }
    long long w = 0;
    if (col < n - 1) {
      w = nxt[col][sz - 1];
    }
    if (f2) {
      w += pre[col][sz - 1]; 
    }
    ret = max(ret, bt(col + 1, 1, 0) + w); //full tower
  }
  //cout << "col, f, f2, ret: " << col << ' ' << f << ' ' << f2 << ' ' << ret << endl; 
  return ret;
}
 
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
  n = N;
  in_col.resize(N);
  for (int i = 0; i < M; ++i) {
    in_col[X[i]].push_back({Y[i], W[i]});
  }
  for (int i = 0; i < N; ++i) {
    sort(in_col[i].begin(), in_col[i].end());
    in_col[i].push_back({N, 0});
  }
  pre.resize(N);
  for (int col = 1; col < N; ++col) {
    pre[col].resize(in_col[col].size());
    for (int i = 0; i < (int) in_col[col].size(); ++i) {
      int ptr = 0; 
      long long sum = 0; 
      while (ptr < (int) in_col[col - 1].size() && in_col[col - 1][ptr].first < in_col[col][i].first) {
        sum += in_col[col - 1][ptr].second; 
        ptr++; 
      }
      pre[col][i] = sum; 
    }
  }
  //cout << "PRE: " << pre[1][1] << endl; 
  nxt.resize(N);
  for (int col = 0; col < N - 1; ++col) {
    nxt[col].resize(in_col[col].size());
    for (int i = 0; i < (int) in_col[col].size(); ++i) {
      int ptr = 0;
      long long sum = 0;
      while (ptr < (int) in_col[col + 1].size() && in_col[col + 1][ptr].first < in_col[col][i].first) {
        sum += in_col[col + 1][ptr].second;
        ptr++;
      }
      nxt[col][i] = sum; 
    }
  }
  dp.resize(N);
  for (int i = 0; i < N; ++i) {
    dp[i].resize(2);
    dp[i][0].assign(2, -1);
    dp[i][1].assign(2, -1);
  }
  long long ans = bt(0, 0, 0);
  return ans; 
}

• Subtask 1: 3 / 3
• Subtask 2: 0 / 6
• Subtask 3: 9 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 17 / 17
• Subtask 7: 14 / 14
• Subtask 8: 0 / 16