Submission #1125999

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125999		ntdaccode	Catfish Farm (IOI22_fish)	C++20	100 / 100	166 ms	50052 KiB

fish

#include<bits/stdc++.h>
#include <vector>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back


using namespace std;

typedef pair<int,long long> ii;
typedef tuple<int,int,int> tp;

const int M = 1e6 + 10;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;

int n, m;


vector<ii> Q[N];
long long f[2][2][N];
long long tmp[2][N], mx[2][2][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 = 1;i <= n; i++) Q[i].pb({0,0});
  for(int i = 0;i < m; i++) {
    X[i]++;
    Y[i]++;
    Q[X[i]].pb({Y[i],W[i]});
  }
  for(int i = 1;i <= n; i++) sort(Q[i].begin(), Q[i].end());
  for(int i = 1;i <= n; i++) {
    int pre = -1;
    int sz = Q[i].size();
    for(int j = 0;j <= sz - 1; j++) {
      auto[pos, val] = Q[i][j];
      if(pre != -1 && pre != pos - 1) {
        Q[i].pb({pos - 1,0});
      }
      pre = pos;
    }
    if(pre != n) Q[i].pb({n,0});
    sort(Q[i].begin(),Q[i].end());
  }

  for(int i = 2;i <= n; i++) {
      vector<ii> pre, cur;
      swap(pre,Q[i - 1]);
      swap(cur,Q[i]);
      //
      long long sum = 0;
      int v = 0;
      for(int u = 0;u <= cur.size() - 1; u++) {
        while(v != pre.size() && pre[v].first < cur[u].first) {
          tmp[0][v] = f[0][i - 1 & 1][v] + sum;
          tmp[1][v] = f[1][i - 1 & 1][v] + sum;
          v++;
        }
        sum += cur[u].second;
      }
      while(v != pre.size()) {
        tmp[0][v] = f[0][i - 1 & 1][v] + sum;
        tmp[1][v] = f[1][i - 1 & 1][v] + sum;
        v++;
      }

      for(int v = pre.size() - 1; v >= 0; v--) {
        for(int e = 0;e <= 1; e++) {
          mx[e][i & 1][v] = max(mx[e][i & 1][v + 1], tmp[e][v]);
        }
      }
      v = 0;
      sum = 0;
      for(int u = 0;u <= cur.size() - 1; u++) {
        while(v != pre.size() && pre[v].first < cur[u].first) v++;
        sum -= cur[u].second;
        f[1][i & 1][u] = max(mx[0][i & 1][v], mx[1][i & 1][v]) + sum;
        //cout << cur[u].second << " ";
        //cout << i << " " << 1 << " " << cur[u].first << " " << f[1][i & 1][u] <<  "\n";
      }
      //

      sum = 0;
      for(int v = pre.size() - 1;v >= 0; v--) {
        tmp[0][v] = f[0][i - 1 & 1][v] + sum;
        tmp[1][v] = f[1][i - 1 & 1][v];
        sum += pre[v].second;
      }
      mx[0][i & 1][0] = tmp[0][0];
      mx[1][i & 1][0] = tmp[1][0];

      for(int v = 1;v <= pre.size() - 1; v++) {
          for(int e = 0;e <= 1; e++) mx[e][i & 1][v] = max(mx[e][i & 1][v - 1], tmp[e][v]);
      }
      sum = 0;
      int u = cur.size() - 1;
      for(int v  = pre.size() - 1;v >= 0; v--) {
          while(u != -1 && pre[v].first <= cur[u].first) {
          f[0][i & 1][u] = max({mx[0][i & 1][v] + sum,mx[1][i & 1][v]});
          //cout << i << " " << cur[u].first << " " << f[0][i & 1][u] << "\n";
          u--;
          }
          sum -= pre[v].second;
          //cout << pre[v].first << " ";
      }
      while(u != -1) {
          f[0][i & 1][u] = max({mx[0][i & 1][0] + sum,mx[1][i & 1][0]});
          //cout << pre[v].first << " "  <<  i << " " << 0 << " " << cur[u].first << " " << f[0][i & 1][u] <<  "\n";
          u--;
      }
      for(int j = 0;j <= pre.size(); j++) {
        f[0][i - 1 & 1][j] = f[1][i - 1 & 1][j] = tmp[0][j] = tmp[1][j] = 0;
      }
      swap(pre,Q[i - 1]);
      swap(cur,Q[i]);
  }
  long long kq = 0;
  for(int i = 0;i <= n; i++) kq = max({kq, f[0][n & 1][i], f[1][n & 1][i]});
  return kq;
}

• 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