Submission #628045

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
628045	2022-08-13T03:54:40 Z	jwvg0425	Catfish Farm (IOI22_fish)	C++17	61 / 100	742 ms	361548 KB

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[3005][3005][3];
i64 val[3005][3005];
i64 psum[3005][3005];
int n;

// type == 0 desc, type == 1 desc top, type == 2 asc
i64 dp(int x, int y, int type)
{
	if (x >= n + 1)
		return 0;

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

	auto& res = table[x][y][type];
	res = 0;

	if (type == 2)
	{
		// 한 칸 더 위 or 오른쪽 위 or 두칸 뛰면서 desc
		if (y < n)
		{
			res = max(res, val[x][y] + dp(x, y + 1, type));
			if (x < n - 1)
				res = max(res, val[x][y] + dp(x + 1, y + 1, type));
		}

		res = max({ res, val[x][y] + dp(x + 2, y, 1), val[x][y] + dp(x + 3, y, 1) });
	}
	else if (type == 1)
	{
		// 내 아래 다 먹고 여기부터 asc로 전환 가능
		if (x <= n - 1)
		{
			auto down = y == 0 ? 0 : psum[x][y - 1];
			res = dp(x, y, 2) + down;
		}

		// 그 외의 경우, 그냥 단순 내림차
		res = max(res, dp(x, y, 0));
	}
	else
	{
		// 단순 내림차 -> 한칸 밑으로 or 오른쪽 한칸 밑으로
		if (y == 0)
		{
			// 맨밑 왔으면 그냥 한칸 옆으로 가면 됨
			res = dp(x + 1, y, 1);
			return res;
		}

		if (x < n - 1 && y < n)
			res = max(res, psum[x][y] + dp(x + 1, y + 1, 2));

		res = val[x][y] + max({ dp(x + 1, y - 1, 1), dp(x, y - 1, 0), psum[x][y - 1] + dp(x + 2, y, 1), psum[x][y-1] + dp(x + 3, y, 1) });
	}

	return res;
}


i64 sub1(vector<int> w)
{
	i64 res = 0;
	for (auto& wi : w)
		res += wi;

	return res;
}

i64 sub2(int m, vector<int> x, vector<int> y, vector<int> w)
{

	i64 res1 = 0, res2 = 0;

	for (int i = 0; i < m; i++)
	{
		if (x[i] == 0)
			res1 += w[i];
		else
			res2 += w[i];
	}

	if (n <= 2)
		return max(res1, res2);

	i64 sums[2][100005] = { 0, };

	for (int i = 0; i < m; i++)
		sums[x[i]][y[i]] += w[i];
	
	for (int xi = 0; xi < 2; xi++)
		for (int yi = 1; yi < n; yi++)
			sums[xi][yi] += sums[xi][yi - 1];

	i64 res = max(res1, res2);

	for (int y = 0; y < n; y++)
		res = max(res, sums[0][y] + res2 - sums[1][y]);

	return res;
}

i64 max_weights(int n_, int m, vector<int> x, vector<int> y, vector<int> w)
{
	n = n_;
	if (all_of(all(x), [](int xi) { return xi % 2 == 0; }))
		return sub1(w);

	if (all_of(all(x), [](int xi) { return xi <= 1; }))
		return sub2(m, x, y, w);

	for (int i = 0; i < m; i++)
		val[x[i] + 1][y[i] + 1] += w[i];

	for (int x = 1; x <= n; x++)
		for (int y = 1; y <= n; y++)
			psum[x][y] += psum[x][y - 1] + val[x][y];

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

	return dp(0, 0, 1);
}

Subtask #1
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	2508 KB	Output is correct
2	Correct	27 ms	3016 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	95 ms	8428 KB	Output is correct
6	Correct	82 ms	8432 KB	Output is correct

Subtask #2
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1748 KB	Output is correct
2	Correct	47 ms	7588 KB	Output is correct
3	Correct	60 ms	8924 KB	Output is correct
4	Correct	28 ms	2400 KB	Output is correct
5	Correct	28 ms	3032 KB	Output is correct
6	Correct	1 ms	1748 KB	Output is correct
7	Correct	1 ms	1748 KB	Output is correct
8	Correct	1 ms	1748 KB	Output is correct
9	Correct	1 ms	1748 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	23 ms	4732 KB	Output is correct
13	Correct	30 ms	5412 KB	Output is correct
14	Correct	24 ms	4728 KB	Output is correct
15	Correct	28 ms	4952 KB	Output is correct
16	Correct	24 ms	4728 KB	Output is correct
17	Correct	27 ms	4948 KB	Output is correct

Subtask #3
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Runtime error	7 ms	360 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #4
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	84 ms	212360 KB	Output is correct
2	Correct	77 ms	212300 KB	Output is correct
3	Correct	1 ms	1748 KB	Output is correct
4	Correct	1 ms	1748 KB	Output is correct
5	Correct	1 ms	1856 KB	Output is correct
6	Correct	1 ms	1748 KB	Output is correct
7	Correct	1 ms	1748 KB	Output is correct
8	Correct	77 ms	212292 KB	Output is correct
9	Correct	82 ms	213808 KB	Output is correct
10	Correct	84 ms	215628 KB	Output is correct
11	Correct	83 ms	213796 KB	Output is correct
12	Correct	84 ms	215580 KB	Output is correct
13	Correct	86 ms	213020 KB	Output is correct
14	Correct	87 ms	215492 KB	Output is correct

Subtask #5
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	84 ms	212360 KB	Output is correct
2	Correct	77 ms	212300 KB	Output is correct
3	Correct	1 ms	1748 KB	Output is correct
4	Correct	1 ms	1748 KB	Output is correct
5	Correct	1 ms	1856 KB	Output is correct
6	Correct	1 ms	1748 KB	Output is correct
7	Correct	1 ms	1748 KB	Output is correct
8	Correct	77 ms	212292 KB	Output is correct
9	Correct	82 ms	213808 KB	Output is correct
10	Correct	84 ms	215628 KB	Output is correct
11	Correct	83 ms	213796 KB	Output is correct
12	Correct	84 ms	215580 KB	Output is correct
13	Correct	86 ms	213020 KB	Output is correct
14	Correct	87 ms	215492 KB	Output is correct
15	Correct	89 ms	215488 KB	Output is correct
16	Correct	86 ms	212956 KB	Output is correct
17	Correct	106 ms	216552 KB	Output is correct
18	Correct	95 ms	216368 KB	Output is correct
19	Correct	95 ms	216888 KB	Output is correct
20	Correct	99 ms	216888 KB	Output is correct
21	Correct	102 ms	216916 KB	Output is correct
22	Correct	120 ms	218380 KB	Output is correct
23	Correct	86 ms	216368 KB	Output is correct
24	Correct	91 ms	216928 KB	Output is correct
25	Correct	82 ms	215504 KB	Output is correct
26	Correct	86 ms	215932 KB	Output is correct

Subtask #6
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	84 ms	212360 KB	Output is correct
2	Correct	77 ms	212300 KB	Output is correct
3	Correct	1 ms	1748 KB	Output is correct
4	Correct	1 ms	1748 KB	Output is correct
5	Correct	1 ms	1856 KB	Output is correct
6	Correct	1 ms	1748 KB	Output is correct
7	Correct	1 ms	1748 KB	Output is correct
8	Correct	77 ms	212292 KB	Output is correct
9	Correct	82 ms	213808 KB	Output is correct
10	Correct	84 ms	215628 KB	Output is correct
11	Correct	83 ms	213796 KB	Output is correct
12	Correct	84 ms	215580 KB	Output is correct
13	Correct	86 ms	213020 KB	Output is correct
14	Correct	87 ms	215492 KB	Output is correct
15	Correct	89 ms	215488 KB	Output is correct
16	Correct	86 ms	212956 KB	Output is correct
17	Correct	106 ms	216552 KB	Output is correct
18	Correct	95 ms	216368 KB	Output is correct
19	Correct	95 ms	216888 KB	Output is correct
20	Correct	99 ms	216888 KB	Output is correct
21	Correct	102 ms	216916 KB	Output is correct
22	Correct	120 ms	218380 KB	Output is correct
23	Correct	86 ms	216368 KB	Output is correct
24	Correct	91 ms	216928 KB	Output is correct
25	Correct	82 ms	215504 KB	Output is correct
26	Correct	86 ms	215932 KB	Output is correct
27	Correct	671 ms	296164 KB	Output is correct
28	Correct	178 ms	228556 KB	Output is correct
29	Correct	721 ms	294128 KB	Output is correct
30	Correct	729 ms	336972 KB	Output is correct
31	Correct	737 ms	337616 KB	Output is correct
32	Correct	190 ms	228676 KB	Output is correct
33	Correct	742 ms	361520 KB	Output is correct
34	Correct	736 ms	361548 KB	Output is correct
35	Correct	710 ms	301636 KB	Output is correct
36	Correct	719 ms	307192 KB	Output is correct

Subtask #7
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Runtime error	7 ms	360 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	2508 KB	Output is correct
2	Correct	27 ms	3016 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	95 ms	8428 KB	Output is correct
6	Correct	82 ms	8432 KB	Output is correct
7	Correct	1 ms	1748 KB	Output is correct
8	Correct	47 ms	7588 KB	Output is correct
9	Correct	60 ms	8924 KB	Output is correct
10	Correct	28 ms	2400 KB	Output is correct
11	Correct	28 ms	3032 KB	Output is correct
12	Correct	1 ms	1748 KB	Output is correct
13	Correct	1 ms	1748 KB	Output is correct
14	Correct	1 ms	1748 KB	Output is correct
15	Correct	1 ms	1748 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	23 ms	4732 KB	Output is correct
19	Correct	30 ms	5412 KB	Output is correct
20	Correct	24 ms	4728 KB	Output is correct
21	Correct	28 ms	4952 KB	Output is correct
22	Correct	24 ms	4728 KB	Output is correct
23	Correct	27 ms	4948 KB	Output is correct
24	Correct	0 ms	212 KB	Output is correct
25	Runtime error	7 ms	360 KB	Execution killed with signal 11
26	Halted	0 ms	0 KB	-

Submission #628045

Compilation message