제출 #1237436

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1237436		madamadam3	메기 농장 (IOI22_fish)	C++20	0 / 100	41 ms	8512 KiB

fish

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

using namespace std;

typedef long long ll;
using vi =vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;

ll sub1(int n, int m, vi &x, vi &y, vl &w, map<pair<int, int>, int> &fish) {
  return accumulate(w.begin(), w.end(), 0LL);
}

ll sub2(int n, int m, vi &x, vi &y, vl &w, map<pair<int, int>, int> &fish) {
  if (n <= 2) {
    ll asum = 0, bsum = 0;
    for (int i = 0; i < m; i++) {
      if (x[i] == 0) asum += w[i];
      else bsum += w[i];
    }

    return max(asum, bsum);
  } else {
    vl prefa(n+1), prefb(n+1);
    for (int i = 1; i <= n; i++) {
      prefa[i] = prefa[i-1];
      prefb[i] = prefb[i-1];

      if (fish.count({0, i-1})) prefa[i] += w[fish[{0, i-1}]];
      if (fish.count({1, i-1})) prefb[i] += w[fish[{1, i-1}]];
    }

    ll ans = prefb[n];
    for (int i = 1; i <= n; i++) {
      ans = max(ans, prefa[i] + prefb[n] - prefb[i]);
    }
    return ans;
  }
}

ll sub3(int n, int m, vi &x, vi &y, vl &w, map<pair<int, int>, int> &fish) {
  vl DP(n+1, 0LL);
  ll running_max = 0;
  
  for (int i = 1; i <= n; i++) {
    ll wp = fish.count({i-2, 0}) ? w[fish[{i-2, 0}]] : 0LL;
    ll wm = fish.count({i-1, 0}) ? w[fish[{i-1, 0}]] : 0LL;
    ll ws = fish.count({i, 0}) ? w[fish[{i, 0}]] : 0LL;

    DP[i] = DP[i-1] + ws - wm;
    if (i > 1) DP[i] = max(DP[i], DP[i-2] + ws);
    if (i > 2) DP[i] = max(DP[i], running_max + wp + ws);

    if (i > 1) running_max = max(running_max, DP[i-2]);
  }

  return *max_element(DP.begin(), DP.end());
}

ll max_weights(int n, int m, vi x, vi y, vi W) {
  vl w(W.begin(), W.end());
  map<pair<int, int>, int> fish; for (int i = 0; i < m; i++) fish[{x[i], y[i]}] = i;
  // for (auto &el : fish) {
  //   cout << el.first.first << " " << el.first.second << " " << el.second << "\n";
  // }
  
  return sub3(n, m, x, y, w, fish);
}

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