Submission #627836

#	Time	Username	Problem	Language	Result	Execution time	Memory
627836		jwvg0425	Catfish Farm (IOI22_fish)	C++17	0 / 100	59 ms	11040 KiB

fish

#include "fish.h"
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second

using namespace std;

template<typename T, typename Pr = less<T>>
using pq = priority_queue<T, vector<T>, Pr>;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

i64 table[305][305];
i64 val[305][305];
int n;

i64 dp(int x, int py)
{
	if (x >= n + 1)
		return 0;

	if (table[x][py] != -1)
		return table[x][py];

	auto& res = table[x][py];
	res = 0;
	i64 nowl = 0;
	i64 nowr = 0;

	for (int y = 0; y <= n; y++)
	{
		if (py < y)
			nowl += val[x - 1][y];

		nowr += val[x][y];

		res = max({ res, nowl + dp(x + 1, y), nowl + dp(x + 2, y), nowl + dp(x + 3, 0) });
	}

	return res;
}

i64 max_weights(int n_, int m, vector<int> x, vector<int> y, vector<int> w)
{
	n = n_;
	for (int i = 0; i < m; i++)
		val[x[i] + 1][y[i] + 1] = w[i];

	memset(table, -1, sizeof(table));

	return dp(1, 0);
}

• 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