제출 #1237418

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1237418		madamadam3	메기 농장 (IOI22_fish)	C++20	0 / 100	54 ms	12864 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) {
  vvl DP(n+1, vl(2, 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;

    // cout << "i: " << i << " wp: " << wp << " wm: " << wm << " ws: " << ws << "\n";

    DP[i][0] = max(DP[i-1][0], DP[i-1][1]);
    DP[i][1] = max(
      DP[i-1][0] + (i > 2 && DP[i-1][0] == DP[i-2][1] ? 0 : wp) + ws,
      DP[i-1][1] - wm + ws
    );

    // cout << "DP[" << i << "][0] = " << DP[i][0] << "\n";
    // cout << "DP[" << i << "][1] = " << DP[i][1] << "\n";
  }

  return max(DP[n][0], DP[n][1]);
}

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