# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
922621 | LucaLucaM | Catfish Farm (IOI22_fish) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#ifndef FISH_CPP_INCLUDED
#define FISH_CPP_INCLUDED
#include "fish.h"
#include <vector>
#include <cstring>
#include <cassert>
#include <iostream>
typedef long long ll;
bool sub1(std::vector<int> v) {
for (const auto &x : v) {
if (x & 1) {
return false;
}
}
return true;
}
long long max_weights(int n, int m, std::vector<int> x, std::vector<int> y,
std::vector<int> w) {
if (sub1(x)) {
return std::accumulate(w.begin(), w.end(), 0);
}
n++;
ll cnt[n + 1][n + 1];
memset(cnt, 0, sizeof(cnt));
for (int i = 0; i < m; i++) {
x[i]++, y[i]++;
x[i] = n - 1 - x[i] + 1;
cnt[x[i]][y[i]] += w[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cnt[i][j] += cnt[i - 1][j];
}
}
ll dp[n + 1][n + 1];
memset(dp, 0, sizeof(dp));
for (int i = 2; i <= n; i++) {
for (int j = 0; j <= (i == n? 0 : n); j++) {
for (int k = 0; k <= (i == 2? 0 : n); k++) {
dp[i][j] = std::max(dp[i][j], dp[i - 2][k] + cnt[i - 1][std::max(j, k)]);
}
}
}
return dp[n][0];
return 0;
}
#endif // FISH_CPP_INCLUDED