Submission #628000

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
628000	2022-08-13T02:58:35 Z	jwvg0425	Catfish Farm (IOI22_fish)	C++17	52 / 100	1000 ms	361868 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 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];

	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
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1103 ms	103316 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	79 ms	212288 KB	Output is correct
2	Execution timed out	1088 ms	105024 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #3
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1094 ms	96984 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	80 ms	212300 KB	Output is correct
2	Correct	79 ms	212348 KB	Output is correct
3	Correct	84 ms	212248 KB	Output is correct
4	Correct	78 ms	212300 KB	Output is correct
5	Correct	88 ms	212268 KB	Output is correct
6	Correct	81 ms	212256 KB	Output is correct
7	Correct	81 ms	212312 KB	Output is correct
8	Correct	78 ms	212344 KB	Output is correct
9	Correct	82 ms	213784 KB	Output is correct
10	Correct	89 ms	215576 KB	Output is correct
11	Correct	80 ms	213780 KB	Output is correct
12	Correct	86 ms	215596 KB	Output is correct
13	Correct	83 ms	212904 KB	Output is correct
14	Correct	84 ms	215500 KB	Output is correct

Subtask #5
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	80 ms	212300 KB	Output is correct
2	Correct	79 ms	212348 KB	Output is correct
3	Correct	84 ms	212248 KB	Output is correct
4	Correct	78 ms	212300 KB	Output is correct
5	Correct	88 ms	212268 KB	Output is correct
6	Correct	81 ms	212256 KB	Output is correct
7	Correct	81 ms	212312 KB	Output is correct
8	Correct	78 ms	212344 KB	Output is correct
9	Correct	82 ms	213784 KB	Output is correct
10	Correct	89 ms	215576 KB	Output is correct
11	Correct	80 ms	213780 KB	Output is correct
12	Correct	86 ms	215596 KB	Output is correct
13	Correct	83 ms	212904 KB	Output is correct
14	Correct	84 ms	215500 KB	Output is correct
15	Correct	88 ms	215568 KB	Output is correct
16	Correct	81 ms	212944 KB	Output is correct
17	Correct	97 ms	216804 KB	Output is correct
18	Correct	98 ms	216716 KB	Output is correct
19	Correct	105 ms	217240 KB	Output is correct
20	Correct	101 ms	217192 KB	Output is correct
21	Correct	103 ms	217140 KB	Output is correct
22	Correct	123 ms	218700 KB	Output is correct
23	Correct	94 ms	216484 KB	Output is correct
24	Correct	99 ms	217156 KB	Output is correct
25	Correct	94 ms	215500 KB	Output is correct
26	Correct	91 ms	216184 KB	Output is correct

Subtask #6
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	80 ms	212300 KB	Output is correct
2	Correct	79 ms	212348 KB	Output is correct
3	Correct	84 ms	212248 KB	Output is correct
4	Correct	78 ms	212300 KB	Output is correct
5	Correct	88 ms	212268 KB	Output is correct
6	Correct	81 ms	212256 KB	Output is correct
7	Correct	81 ms	212312 KB	Output is correct
8	Correct	78 ms	212344 KB	Output is correct
9	Correct	82 ms	213784 KB	Output is correct
10	Correct	89 ms	215576 KB	Output is correct
11	Correct	80 ms	213780 KB	Output is correct
12	Correct	86 ms	215596 KB	Output is correct
13	Correct	83 ms	212904 KB	Output is correct
14	Correct	84 ms	215500 KB	Output is correct
15	Correct	88 ms	215568 KB	Output is correct
16	Correct	81 ms	212944 KB	Output is correct
17	Correct	97 ms	216804 KB	Output is correct
18	Correct	98 ms	216716 KB	Output is correct
19	Correct	105 ms	217240 KB	Output is correct
20	Correct	101 ms	217192 KB	Output is correct
21	Correct	103 ms	217140 KB	Output is correct
22	Correct	123 ms	218700 KB	Output is correct
23	Correct	94 ms	216484 KB	Output is correct
24	Correct	99 ms	217156 KB	Output is correct
25	Correct	94 ms	215500 KB	Output is correct
26	Correct	91 ms	216184 KB	Output is correct
27	Correct	639 ms	296132 KB	Output is correct
28	Correct	177 ms	228880 KB	Output is correct
29	Correct	702 ms	294444 KB	Output is correct
30	Correct	720 ms	337236 KB	Output is correct
31	Correct	728 ms	337720 KB	Output is correct
32	Correct	177 ms	228860 KB	Output is correct
33	Correct	720 ms	361720 KB	Output is correct
34	Correct	729 ms	361868 KB	Output is correct
35	Correct	721 ms	301724 KB	Output is correct
36	Correct	709 ms	307496 KB	Output is correct

Subtask #7
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1094 ms	96984 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1103 ms	103316 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Submission #628000

Compilation message