Submission #1237387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237387		madamadam3	Catfish Farm (IOI22_fish)	C++20	6 / 100	173 ms	30012 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 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;
  
  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;
  }
}

• Subtask 1: 0 / 3
• Subtask 2: 6 / 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