# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
837929 | joylintp | Catfish Farm (IOI22_fish) | C++17 | 852 ms | 2097152 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.
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W)
{
vector<vector<pair<int, int>>> fish(N);
for (int i = 0; i < M; i++)
fish[X[i]].push_back(make_pair(Y[i], W[i]));
for (int i = 0; i < N; i++)
sort(fish[i].begin(), fish[i].end());
vector<vector<vector<long long>>> dp(N, vector<vector<long long>>(N + 1, vector<long long>(N + 1)));
for (int x = 0; x <= N; x++)
{
int fid = 0;
for (int y = 1; y <= N; y++)
{
dp[0][x][y] = dp[0][x][y - 1];
if (fid < fish[0].size() && fish[0][fid].first + 1 == y)
{
if (fish[0][fid].first >= x)
dp[0][x][y] += fish[0][fid].second;
fid++;
}
}
}
for (int i = 1; i < N - 1; i++)
for (int x = 0; x <= N; x++)
{
for (int j = 0; j <= N; j++)
dp[i][x][0] = max(dp[i][x][0], dp[i - 1][j][x]);
int fid = 0;
for (int y = 1; y <= N; y++)
{
dp[i][x][y] = dp[i][x][y - 1];
if (fid < fish[i].size() && fish[i][fid].first + 1)
{
if (fish[i][fid].first >= x)
dp[i][x][y] += fish[i][fid].second;
fid++;
}
}
}
long long ret = 0;
for (int x = 0; x <= N; x++)
{
long long now = 0;
for (auto &p : fish[N - 1])
if (p.first >= x)
break;
else
now += p.second;
int fid = 0;
for (int y = 0; y <= N; y++)
{
if (fid < fish[N - 1].size() && fish[N - 1][fid].first + 1 == y && y < x + 1)
now -= fish[N - 1][fid].second;
ret = max(ret, dp[N - 2][x][y] + now);
}
}
return ret;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |