Submission #733154

#	Time	Username	Problem	Language	Result	Execution time	Memory
733154		puppy	Catfish Farm (IOI22_fish)	C++17	100 / 100	453 ms	95028 KiB

fish

#include "fish.h"

#include <vector>
#include <algorithm>
#include <iostream>
#define int long long
using namespace std;

vector<pair<int, int>> adj[100005];
vector<pair<int, int>> prf[100005];
const long long inf = 1e18;
int _N;
int get_prfsum(int X, int to)
{
    if (X <= 0 || _N+1 <= X) return 0;
    return (*--lower_bound(prf[X].begin(), prf[X].end(), make_pair(to, inf))).second;
}
vector<int> dp[100005][3];
vector<int> suf[100005];
vector<int> prf0[100005], prf1[100005], suf0[100005];
vector<int> cpx[100005];
long long max_weights(signed N, signed M, std::vector<signed> X, std::vector<signed> Y,
                      std::vector<signed> W) {
  _N= N;
  for (int i = 0; i < M; i++) {
    adj[X[i]+1].push_back(make_pair(Y[i] + 2, W[i]));
  }
  for (int i = 1; i <= N; i++) sort(adj[i].begin(), adj[i].end());
  for (int i = 1; i <= N; i++) {
    prf[i].resize(adj[i].size() + 1);
    prf[i][0] = make_pair(0, 0);
    for (int k = 1; k <= adj[i].size(); k++) {
        prf[i][k] = make_pair(adj[i][k-1].first, adj[i][k-1].second + prf[i][k-1].second);
    }
  }
  cpx[0].push_back(0);
  for (int i = 1; i <= N; i++) {
    cpx[i].push_back(0);
    for (pair<int, int> p:adj[i]) cpx[i].push_back(p.first - 1);
    cpx[i].push_back(N+1);
  }
  for (int i = 1; i <= N; i++) {
    dp[i][0].resize(cpx[i].size());
    dp[i][1].resize(cpx[i].size());
    dp[i][2].resize(cpx[i-1].size());
    suf[i].resize(dp[i][0].size());
    prf0[i].resize(dp[i][0].size());
    prf1[i].resize(dp[i][2].size());
    suf0[i].resize(dp[i][2].size());
  }
  for (int i = 1; i <= N; i++) {
    if (i >= 2) {
        for (int j = 0; j < (int)dp[i-1][2].size(); j++) dp[i][2][0] = max(dp[i][2][0], dp[i-1][2][j]);
        for (int j = 1; j < (int)dp[i][2].size(); j++) {
            dp[i][2][j] = max(dp[i-1][0][j], dp[i-1][1][j]) + get_prfsum(i, cpx[i-1][j]);
        }
        for (int j = 1; j < (int)dp[i][1].size(); j++) {
            int height = cpx[i][j]; //height까지 끌어올리기
            //height보다 더 '큰' 최초의 인덱스 k를 찾자
            int low = upper_bound(cpx[i-1].begin(), cpx[i-1].end(), height) - cpx[i-1].begin();
            if (low == cpx[i-1].size()) {
                dp[i][1][j] = -inf;
                continue;
            }
            dp[i][1][j] = suf[i-1][low] - get_prfsum(i, cpx[i][j]);
        }
        for (int j = 1; j < (int)dp[i][0].size(); j++) {
            int ord = upper_bound(cpx[i-1].begin(), cpx[i-1].end(), cpx[i][j]) - cpx[i-1].begin();
            int M1 = ord == 1 ? -inf : (prf0[i-1][ord-1] + get_prfsum(i-1, cpx[i][j]));
            int ord2 = upper_bound(cpx[i-2].begin(), cpx[i-2].end(), cpx[i][j]) - cpx[i-2].begin();
            int M2 = prf1[i-1][ord2-1] + get_prfsum(i-1, cpx[i][j]);
            int M3 = (i == 2 || ord2 >= cpx[i-2].size()) ? -inf : suf0[i-1][ord2];
            dp[i][0][j] = max({M1, M2, M3});
        }
    }

    for (int j = 1; j < (int)dp[i][1].size(); j++) {
        prf0[i][j] = dp[i][0][j] - get_prfsum(i, cpx[i][j]);
        suf[i][j] = max(dp[i][0][j], dp[i][1][j]) + get_prfsum(i+1, cpx[i][j]);
    }
    for (int j = 0; j < (int)dp[i][2].size(); j++) {
        prf1[i][j] = dp[i][2][j] - get_prfsum(i, cpx[i-1][j]);
        suf0[i][j] = dp[i][2][j];
    }
    for (int j = 2; j < (int)dp[i][1].size(); j++) prf0[i][j] = max(prf0[i][j], prf0[i][j-1]);
    for (int j = 1; j < (int)dp[i][2].size(); j++) prf1[i][j] = max(prf1[i][j], prf1[i][j-1]);
    for (int j = (int)dp[i][2].size() - 2; j >= 0; j--) suf0[i][j] = max(suf0[i][j], suf0[i][j+1]);
    for (int j = (int)dp[i][1].size() - 2; j >= 1; j--) suf[i][j] = max(suf[i][j], suf[i][j+1]);
  }
  int ans = 0;
  for (int i = 1; i < (int)dp[N][0].size(); i++) {
    ans = max(ans, dp[N][0][i]);
  }
  for (int i = 1; i < (int)dp[N][1].size(); i++) ans = max(ans, dp[N][1][i]);
  for (int i = 0; i < (int)dp[N][2].size(); i++) ans = max(ans, dp[N][2][i]);
  return ans;
}

Compilation message (stderr)

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:32:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int k = 1; k <= adj[i].size(); k++) {
      |                     ~~^~~~~~~~~~~~~~~~
fish.cpp:61:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |             if (low == cpx[i-1].size()) {
      |                 ~~~~^~~~~~~~~~~~~~~~~~
fish.cpp:72:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             int M3 = (i == 2 || ord2 >= cpx[i-2].size()) ? -inf : suf0[i-1][ord2];
      |                                 ~~~~~^~~~~~~~~~~~~~~~~~

• 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