제출 #1234647

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1234647		rxlfd314	메기 농장 (IOI22_fish)	C++20	100 / 100	165 ms	50028 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

constexpr ll INF = 1e18;

ll max_weights(int N, int M, vt<int> X, vt<int> Y, vt<int> W) {
  vt<vt<arl2>> P(N+1);
  FOR(i, 0, M-1) {
    X[i]++, Y[i]++;
    P[X[i]].push_back({Y[i], W[i]});
  }
  vt<vt<arl2>> dp0(N+1), dp1(N+1);
  FOR(i, 0, N) {
    P[i].push_back({0, 0});
    P[i].push_back({N+1, 0});
    sort(all(P[i]));
    FOR(j, 1, size(P[i])-1)
      P[i][j][1] += P[i][j-1][1];
    FOR(j, 0, size(P[i])-1) {
      dp0[i].push_back({P[i][j][0]-1, -INF});
      dp1[i].push_back({P[i][j][0]-1, -INF});
    }
  }
  dp0[0][0][0] = dp1[0][0][0] = 0;
  ll ans = 0;
  FOR(i, 1, N) {
    int ptr2 = 0, ptr1 = 0;
    ll mx = 0;
    FOR(x, 0, size(dp0[i]) - 1) {
      auto &[j, v0] = dp0[i][x];
      auto &[_, v1] = dp1[i][x];
      if (i > 1) {
        for (; ptr2 < size(dp0[i-2]) && dp0[i-2][ptr2][0] <= j; ptr2++)
          mx = max({mx, dp0[i-2][ptr2][1], dp1[i-2][ptr2][1]});
      }
      for (; ptr1 < size(P[i-1]) && P[i-1][ptr1][0] <= j; ptr1++);
      v1 = v0 = max(v0, mx + (ptr1 ? P[i-1][ptr1-1][1] : 0));
    }
    if (i > 1)
      ptr2 = size(dp0[i-2]) - 1;
    ptr1 = size(P[i-1]) - 1;
    mx = -INF;
    ROF(x, size(dp0[i]) - 1, 0) {
      auto &[j, v0] = dp0[i][x];
      auto &[_, v1] = dp1[i][x];
      if (i > 1) {
        for (; ptr2 >= 0 && dp0[i-2][ptr2][0] > j; ptr2--) {
          for (; ptr1 >= 0 && P[i-1][ptr1][0] > dp0[i-2][ptr2][0]; ptr1--);
          mx = max(mx, max(dp0[i-2][ptr2][1], dp1[i-2][ptr2][1]) + (ptr1 >= 0 ? P[i-1][ptr1][1] : 0));
        }
      }
      v1 = v0 = max(v0, mx);
    }
    ptr1 = 0, ptr2 = 0;
    int ptr3 = 0;
    mx = -INF;
    FOR(x, 0, size(dp0[i]) - 1) {
      auto &[j, v0] = dp0[i][x];
      for (; ptr1 < size(dp0[i-1]) && dp0[i-1][ptr1][0] <= j; ptr1++) {
        for (; ptr2 < size(P[i-1]) && P[i-1][ptr2][0] <= dp0[i-1][ptr1][0]; ptr2++);
        mx = max(mx, dp0[i-1][ptr1][1] - (ptr2 ? P[i-1][ptr2-1][1] : 0));
      }
      for (; ptr3 < size(P[i-1]) && P[i-1][ptr3][0] <= j; ptr3++);
      v0 = max(v0, mx + (ptr3 ? P[i-1][ptr3-1][1] : 0));
      ans = max(ans, v0);
    }
    ptr1 = size(dp0[i-1]) - 1;
    ptr3 = ptr2 = size(P[i]) - 1;
    mx = -INF;
    ROF(x, size(dp1[i]) - 1, 0) {
      auto &[j, v1] = dp1[i][x];
      for (; ptr1 >= 0 && dp0[i-1][ptr1][0] >= j; ptr1--) {
        for (; ptr2 >= 0 && P[i][ptr2][0] > dp0[i-1][ptr1][0]; ptr2--);
        mx = max(mx, max(dp0[i-1][ptr1][1], dp1[i-1][ptr1][1]) + (ptr2 >= 0 ? P[i][ptr2][1] : 0));
      }
      for (; ptr3 >= 0 && P[i][ptr3][0] > j; ptr3--);
      v1 = max(v1, mx - (ptr3 >= 0 ? P[i][ptr3][1] : 0));
      ans = max(ans, v1);
    }
  }
  return ans;
}

/*
ll max_weights(int N, int M, vt<int> X, vt<int> Y, vt<int> W) {
  vt<vt<ll>> P(N+1, vt<ll>(N+1));
  FOR(i, 0, M-1) {
    X[i]++, Y[i]++;
    P[X[i]][Y[i]] = W[i];
  }
  FOR(i, 1, N)
    FOR(j, 1, N)
      P[i][j] += P[i][j-1];
  vt<vt<arl2>> dp(N+1, vt<arl2>(N+1, {-INF, -INF}));
  dp[0][0][0] = dp[0][0][1] = 0;
  ll ans = 0;
  FOR(i, 1, N)
    FOR(j, 0, N) {
      FOR(k, 0, j)
        dp[i][j][0] = max(dp[i][j][0], (i > 1 ? max(dp[i-2][k][0], dp[i-2][k][1]) : 0) + P[i-1][j]);
      FOR(k, j+1, N)
        dp[i][j][0] = max(dp[i][j][0], (i > 1 ? max(dp[i-2][k][0], dp[i-2][k][1]) : -INF) + P[i-1][k]);
      dp[i][j][1] = dp[i][j][0];
      FOR(k, 0, j)
        dp[i][j][0] = max(dp[i][j][0], dp[i-1][k][0] + P[i-1][j] - P[i-1][k]);
      FOR(k, j, N)
        dp[i][j][1] = max(dp[i][j][1], max(dp[i-1][k][0], dp[i-1][k][1]) + P[i][k] - P[i][j]);
      ans = max({ans, dp[i][j][0], dp[i][j][1]});
    }
  return ans;
}*/

• 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