Submission #838856

#	Time	Username	Problem	Language	Result	Execution time	Memory
838856		taher	Catfish Farm (IOI22_fish)	C++17	100 / 100	892 ms	193104 KiB

fish

#include <bits/stdc++.h>
#include "fish.h"

using namespace std;

long long dp[700000][3][2];
bool vis[700000][3][2];

long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
  vector<vector<int>> at(n);
  vector<vector<int>> ids(n);
  for (int i = 0; i < m; i++) {
    at[x[i]].push_back(y[i]); 
    ids[x[i]].push_back(i);
  }
  
  
  for (int i = 0; i < n; i++) {
    if (at[i].empty()) {
      continue;
    }
    sort(ids[i].begin(), ids[i].end(), [&](int a, int b) {
      return y[a] < y[b];    
    });
    sort(at[i].begin(), at[i].end()); 
  }
  
  vector<vector<long long>> pref(n);
  for (int i = 0; i < n; i++) {
    if (at[i].empty()) {
      continue; 
    }
    pref[i].resize((int) at[i].size());
    pref[i][0] = 1LL * w[ids[i][0]];
    for (int j = 1; j < (int) at[i].size(); j++) {
      pref[i][j] = pref[i][j - 1] + w[ids[i][j]];
    }
  }
  
  vector<vector<int>> endpoints(n);
  for (int i = 0; i < n; i++) {
    if (i > 0) {
      for (auto v : at[i - 1]) {
        endpoints[i].push_back(v); 
      } 
    }
    if (i < n - 1) {
      for (auto v : at[i + 1]) {
        endpoints[i].push_back(v); 
      }            
    }
    endpoints[i].push_back(-1);
    
    sort(endpoints[i].begin(), endpoints[i].end());
    endpoints[i].erase(unique(endpoints[i].begin(), endpoints[i].end()), endpoints[i].end());
  }
  
  int current = 0;
  vector<vector<int>> coords(n);
  for (int i = 0; i < n; i++) {
    coords[i].resize((int) endpoints[i].size());
    for (int j = 0; j < (int) endpoints[i].size(); j++) {
      coords[i][j] = current++; 
    }
  }  
  
  auto Count = [&](int col, int from, int to) {
    int xx = upper_bound(at[col].begin(), at[col].end(), from) - at[col].begin();
    int yy = upper_bound(at[col].begin(), at[col].end(), to) - at[col].begin();
    yy--;
    
    if (xx <= yy) {
      assert(yy < (int) at[col].size());
      long long s = pref[col][yy];
      if (xx > 0) {
        s -= pref[col][xx - 1]; 
      }
      return s;        
    }
    return 0LL;
  };
  
  /*
    0: undef
    1: increasing
    2: decreasing
  */
  
  // vector<vector<vector<long long>>> dp(current, vector<vector<long long>> (3, vector<long long> (2, -1)));
  
  function<long long(int, int, int, int)> DP = [&](int col, int id, int state, int used_dec) {
    
    if (vis[coords[col][id]][state][used_dec]) {
      return dp[coords[col][id]][state][used_dec]; 
    }
    
    long long ans = 0;
    int current_height = endpoints[col][id];
    if (state == 1) {
      if (id + 1 < (int) endpoints[col].size()) {
        long long cnt = Count(col - 1, current_height, endpoints[col][id + 1]);
        ans = max(ans, DP(col, id + 1, 1, used_dec) + cnt); 
      }      
    } else if (state == 2) {
      if (id - 1 > 0) {
        long long cnt = Count(col, endpoints[col][id - 1], current_height);
        ans = max(ans, DP(col, id - 1, 2, used_dec) + cnt);
      } 
    } else {
      if (id + 1 < (int) endpoints[col].size()) {
        ans = max(ans, DP(col, id + 1, 0, used_dec)); 
      }
    }
    
    if (col + 1 < n) {
      if (!used_dec) {
        int nid = lower_bound(endpoints[col + 1].begin(), endpoints[col + 1].end(), current_height) - endpoints[col + 1].begin();
        if (nid < (int) endpoints[col + 1].size()) {
          ans = max(ans, DP(col + 1, nid, 1, used_dec) + Count(col, current_height, endpoints[col + 1][nid])); 
        }
      }
      int nid = upper_bound(endpoints[col + 1].begin(), endpoints[col + 1].end(), current_height) - endpoints[col + 1].begin();
      --nid;
      if (nid > 0) {
        ans = max(ans, DP(col + 1, nid, 2, 1) + Count(col + 1, endpoints[col + 1][nid], current_height));
      }
      
      ans = max(ans, Count(col + 1, -1, current_height));
    }
    if (col + 2 < n) {
      int nid = lower_bound(endpoints[col + 2].begin(), endpoints[col + 2].end(), current_height) - endpoints[col + 2].begin();
      if (nid < (int) endpoints[col + 2].size()) {
        ans = max(ans, DP(col + 2, nid, 1, 0) + Count(col + 1, -1, endpoints[col + 2][nid]));
      }
      nid = 0;
      ans = max(ans, DP(col + 2, nid, 0, 0) + Count(col + 1, -1, current_height));
    }
    vis[coords[col][id]][state][used_dec] = true;
    return dp[coords[col][id]][state][used_dec] = ans;
  };
  
  long long res = DP(0, 0, 0, 0);
  return res;
}

• 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