제출 #657248

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
657248		lumibons	메기 농장 (IOI22_fish)	C++17	100 / 100	481 ms	60260 KiB

fish

#include "fish.h"

#include <bits/stdc++.h>

using namespace std;

#define sz(x) ((int) (x).size())
typedef long long ll;

ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
  vector<vector<int>> p(n + 3);
  for (int i = 0; i < m; i++)
    for (int d = x[i] == 0 ? 0 : -1; d < (x[i] == n - 1 ? 1 : 2); d++)
      p[x[i] + d + 1].push_back(y[i]);
  vector<vector<ll>> ws(n + 3);
  for (int i = 0; i < n + 3; i++) {
    p[i].push_back(-1);
    sort(p[i].begin(), p[i].end());
    p[i].erase(unique(p[i].begin(), p[i].end()), p[i].end());
    ws[i].resize(sz(p[i]));
  }
  for (int i = 0; i < m; i++) {
    int j = (int) (lower_bound(p[x[i] + 1].begin(), p[x[i] + 1].end(), y[i]) - p[x[i] + 1].begin());
    ws[x[i] + 1][j] += w[i];
  }
  for (int i = 0; i < n + 3; i++)
    for (int j = 1; j < sz(ws[i]); j++)
      ws[i][j] += ws[i][j - 1];
  auto weightBelow = [&](int i, int j) {
    int k = (int) (upper_bound(p[i].begin(), p[i].end(), j) - p[i].begin()) - 1;
    return ws[i][k];
  };
  vector<vector<ll>> dpu(n + 3), dpd(n + 3);
  dpu[0].push_back(0);
  dpd[0].push_back(0);
  for (int i = 1; i < n + 2; i++) {
    dpu[i].resize(sz(p[i]));
    dpd[i].resize(sz(p[i]));
    ll mdp = 0;
    for (int j = 0, k = 0; j < sz(p[i]); j++) {
      while (k < sz(p[i - 1]) && p[i - 1][k] <= p[i][j])
        mdp = max(mdp, dpu[i - 1][k] - weightBelow(i - 1, p[i - 1][k])), k++;
      dpu[i][j] = mdp + weightBelow(i - 1, p[i][j]);
    }
    mdp = 0;
    for (int j = sz(p[i]) - 1, k = sz(p[i - 1]) - 1; j >= 0; j--) {
      while (k >= 0 && p[i - 1][k] >= p[i][j])
        mdp = max(mdp, dpd[i - 1][k]), k--;
      dpd[i][j] = max(dpd[i][j], mdp - weightBelow(i, p[i][j]) + weightBelow(i + 1, p[i][j]));
    }
    if (i > 1) {
      mdp = 0;
      for (int j = 0, k = 0; j < sz(p[i]); j++) {
        while (k < sz(p[i - 2]) && p[i - 2][k] <= p[i][j])
          mdp = max(mdp, dpd[i - 2][k] - weightBelow(i - 1, p[i - 2][k])), k++;
        dpu[i][j] = max(dpu[i][j], mdp + weightBelow(i - 1, p[i][j]));
      }
      mdp = 0;
      for (int j = sz(p[i]) - 1, k = sz(p[i - 2]) - 1; j >= 0; j--) {
        while (k >= 0 && p[i - 2][k] >= p[i][j])
          mdp = max(mdp, dpd[i - 2][k]), k--;
        dpu[i][j] = max(dpu[i][j], mdp);
      }
    }
    for (int j = 0; j < sz(p[i]); j++)
      dpd[i][j] = max(dpd[i][j], dpu[i][j] + weightBelow(i + 1, p[i][j]));
  }
  return dpd[n + 1][0];
}

• 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