제출 #659589

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
659589		peijar	메기 농장 (IOI22_fish)	C++17	14 / 100	1097 ms	6828 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 301;
const int INF = 1e18;

int dp[MAXN][MAXN][2];

int max_weights(signed N, signed M, vector<signed> X, vector<signed> Y,
                vector<signed> W) {

  if (N > MAXN)
    return 0;
  vector<vector<pair<int, int>>> onCol(N);
  vector<vector<int>> prefSum(N);
  for (int i = 0; i < M; ++i)
    onCol[X[i]].emplace_back(Y[i] + 1, W[i]);
  for (int i = 0; i < N; ++i) {
    sort(onCol[i].begin(), onCol[i].end());
    prefSum[i].resize(onCol[i].size() + 1);
    for (int j = 0; j < (int)onCol[i].size(); ++j)
      prefSum[i][j + 1] = prefSum[i][j] + onCol[i][j].second;
  }

  int sol = 0;
  for (int i = 1; i < N; ++i)
    for (int h = 0; h <= N; ++h) {
      // 1
      for (int oldH = h + 1; oldH <= N; ++oldH) {
        int lo = upper_bound(onCol[i].begin(), onCol[i].end(), pair(h, INF)) -
                 onCol[i].begin();
        int up =
            upper_bound(onCol[i].begin(), onCol[i].end(), pair(oldH, INF)) -
            onCol[i].begin();
        dp[i][h][1] =
            max(dp[i][h][1], prefSum[i][up] - prefSum[i][lo] +
                                 max(dp[i - 1][oldH][0], dp[i - 1][oldH][1]));
      }
      // 0
      for (int oldH = 0; oldH <= N; ++oldH) {
        if (oldH >= h)
          dp[i][h][0] =
              max(dp[i][h][0], max(dp[i - 1][oldH][0], dp[i - 1][oldH][1]));
        else {
          int lo = upper_bound(onCol[i - 1].begin(), onCol[i - 1].end(),
                               pair(oldH, INF)) -
                   onCol[i - 1].begin();
          int up = upper_bound(onCol[i - 1].begin(), onCol[i - 1].end(),
                               pair(h, INF)) -
                   onCol[i - 1].begin();
          dp[i][h][0] =
              max(dp[i][h][0],
                  dp[i - 1][oldH][0] + prefSum[i - 1][up] - prefSum[i - 1][lo]);
        }
      }
      sol = max({sol, dp[i][h][0], dp[i][h][1]});
    }
  return sol;
}

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