Submission #753666

#	Time	Username	Problem	Language	Result	Execution time	Memory
753666		midi	Catfish Farm (IOI22_fish)	C++17	0 / 100	1173 ms	2097152 KiB

fish

#include <bits/stdc++.h>
using namespace std;
	
typedef long long ll;
typedef vector<ll> vcll;
typedef pair<ll, ll> prll;
	
#define f0r(i, a, n) for (i = a; i < n; i++)
#define f1r(i, a, n) for (i = a; i <= n; i++)
#define r0f(i, n, a) for (i = n; i > a; i--)
#define r1f(i, n, a) for (i = n; i >= a; i--)
	
#define mxN	100000
#define mxM 300000
	
#define rest_input int n, int m, vector<int> x, vector<int> y, vector<int> w
#define throw_input n, m, x, y, w
	
#define allocate(type, size) (type *)malloc((size) * sizeof(type))
	
ll n, m;

ll **grid;
ll **psa;

void build_grid(rest_input)
{
	grid = allocate(ll *, n + 10);
	ll i, j;
	f0r(i, 0, n) grid[i] = allocate(ll, n + 10);
	
	f0r(i, 0, n) f0r(j, 0, n) grid[i][j] = 0;
	
	f0r(i, 0, m)
		grid[x[i]][y[i]] = w[i];
}

void build_psa(ll n)
{
	psa = allocate(ll *, n + 10);
	psa++;
	ll i, j;
	f0r(i, -1, n) psa[i] = allocate(ll, n + 10);
	f0r(i, -1, n) psa[i]++;
	f0r(j, -1, n) psa[-1][j] = 0;
	
	f0r(i, 0, n)
	{
		ll run_max = 0;
		// printf("at i: %lli\n", i);
		f0r(j, -1, n)
		{
			// printf("on j: %lli : %lli\n", j, run_max);
			psa[i][j] = run_max;
			run_max += grid[i][j + 1];
		}
	}
}

ll C(ll i, ll j3, ll j2, ll j)
{ 
	ll j4 = max(j3, j2);
	
	ll sum = 0;
	if (j < j2) sum += psa[i][j2] - psa[i][j];
	if (j > j4) sum += psa[i - 1][j] - psa[i - 1][j4];
	
	return sum;
}

ll ***memoi;
// bool ***memo_bool;
void init_memoi(ll n)
{
	memoi = allocate(ll **, n + 10);
	// memoi++;
	// memo_bool = allocate(bool **, n + 10);
	ll i, j;
	
	f0r(i, -1, n + 10)
	{
		memoi[i] = allocate(ll *, n + 10);
		memoi[i]++;
	}
	// f0r(i, 0, n + 10) memo_bool[i] = allocate(bool *, n + 10);
	f0r(i, -1, n + 10) f0r(j, -1, n + 10)
	{
		memoi[i][j] = allocate(ll, n + 10);
		memoi[i][j]++;
	}
	// f0r(i, 0, n + 10) f0r(j, 0, n + 10) memo_bool[i][j] = allocate(bool, n + 10);
	
	ll k;
	// f0r(i, 0, n + 10) f0r(j, 0, n + 10) f0r(k, 0, n + 10) memo_bool[i][j][k] = 0;
	f0r(i, 0, n) f0r(j, -1, n) f0r(k, -1, n) memoi[i][j][k] = -1;
}

ll call_count = 0;
ll subcall_count = 0;
ll memo_count = 0;
ll zero_count = 0;
ll reduct_count = 0;
ll notred_count = 0;

ll dp(ll i, ll j2, ll j3, ll n)
{
	call_count++;
	if (i == n) return 0;
	
	if (j3 < j2) j3 = j2;
	ll &t = memoi[i][j2][j3];
	if (t != -1) return t;
	
	ll maximum = -1;
	ll j;
	
	f0r(j, -1, n) // incl.
	{
		ll v = dp(i + 1, j, j2, n) + C(i, j3, j2, j);
		if (maximum < v) maximum = v;
	}
	
	return (t = maximum);
}

int64_t max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w)
{
	build_grid(throw_input);
	build_psa(n);
	init_memoi(n);
	ll ans = dp(0, -1, n - 1, n);
	// printf("n: %lli\n", (ll)n);
	
	return ans;
}

/*
int main()
{
	int n = 5;
	cin >> n;
	int m = 4;

	vcll x = {0, 1, 4, 3};
	vcll y = {2, 1, 4, 3};
	vcll w = {5, 2, 1, 3};

	// vcll x = {0, 1};
	// vcll y = {1, 0};
	// vcll w = {2, 3};

	m = x.size();
	
	printf("real: %lli\n", (long long)max_weights(n, m, x, y, w));
	printf("call count: %lli\n", call_count);
	printf("subcall count: %lli\n", subcall_count);
	printf("memo count: %lli\n", memo_count);
	printf("zero count: %lli\n", zero_count);
	printf("reduct count: %lli\n", reduct_count);
	printf("notred count: %lli\n", notred_count);
}

*/

• 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