Submission #627908

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
627908	2022-08-13T00:52:38 Z	jwvg0425	Catfish Farm (IOI22_fish)	C++17	14 / 100	1000 ms	218316 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));
			if (x < n - 2)
				res = max(res, val[x][y] + dp(x + 2, 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;
		}

		res = max({ val[x][y] + dp(x + 1, y - 1, 1), val[x][y] + dp(x + 2, y - 1, 1), val[x][y] + dp(x, y - 1, 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];

	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	1078 ms	95872 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	102 ms	212276 KB	Output is correct
2	Execution timed out	1077 ms	94612 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	1090 ms	86192 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	77 ms	212280 KB	Output is correct
2	Correct	80 ms	212376 KB	Output is correct
3	Correct	84 ms	212368 KB	Output is correct
4	Correct	84 ms	212300 KB	Output is correct
5	Correct	84 ms	212348 KB	Output is correct
6	Correct	83 ms	212268 KB	Output is correct
7	Correct	83 ms	212332 KB	Output is correct
8	Correct	82 ms	212288 KB	Output is correct
9	Correct	97 ms	213780 KB	Output is correct
10	Correct	93 ms	215500 KB	Output is correct
11	Correct	81 ms	213692 KB	Output is correct
12	Correct	85 ms	215560 KB	Output is correct
13	Correct	79 ms	212940 KB	Output is correct
14	Correct	85 ms	215552 KB	Output is correct

Subtask #5
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	77 ms	212280 KB	Output is correct
2	Correct	80 ms	212376 KB	Output is correct
3	Correct	84 ms	212368 KB	Output is correct
4	Correct	84 ms	212300 KB	Output is correct
5	Correct	84 ms	212348 KB	Output is correct
6	Correct	83 ms	212268 KB	Output is correct
7	Correct	83 ms	212332 KB	Output is correct
8	Correct	82 ms	212288 KB	Output is correct
9	Correct	97 ms	213780 KB	Output is correct
10	Correct	93 ms	215500 KB	Output is correct
11	Correct	81 ms	213692 KB	Output is correct
12	Correct	85 ms	215560 KB	Output is correct
13	Correct	79 ms	212940 KB	Output is correct
14	Correct	85 ms	215552 KB	Output is correct
15	Correct	89 ms	215440 KB	Output is correct
16	Correct	96 ms	212956 KB	Output is correct
17	Correct	97 ms	216652 KB	Output is correct
18	Correct	103 ms	216392 KB	Output is correct
19	Correct	93 ms	216940 KB	Output is correct
20	Correct	113 ms	216896 KB	Output is correct
21	Correct	101 ms	216864 KB	Output is correct
22	Correct	108 ms	218316 KB	Output is correct
23	Incorrect	92 ms	216400 KB	1st lines differ - on the 1st token, expected: '3061077668538', found: '3060654583637'
24	Halted	0 ms	0 KB	-

Subtask #6
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	77 ms	212280 KB	Output is correct
2	Correct	80 ms	212376 KB	Output is correct
3	Correct	84 ms	212368 KB	Output is correct
4	Correct	84 ms	212300 KB	Output is correct
5	Correct	84 ms	212348 KB	Output is correct
6	Correct	83 ms	212268 KB	Output is correct
7	Correct	83 ms	212332 KB	Output is correct
8	Correct	82 ms	212288 KB	Output is correct
9	Correct	97 ms	213780 KB	Output is correct
10	Correct	93 ms	215500 KB	Output is correct
11	Correct	81 ms	213692 KB	Output is correct
12	Correct	85 ms	215560 KB	Output is correct
13	Correct	79 ms	212940 KB	Output is correct
14	Correct	85 ms	215552 KB	Output is correct
15	Correct	89 ms	215440 KB	Output is correct
16	Correct	96 ms	212956 KB	Output is correct
17	Correct	97 ms	216652 KB	Output is correct
18	Correct	103 ms	216392 KB	Output is correct
19	Correct	93 ms	216940 KB	Output is correct
20	Correct	113 ms	216896 KB	Output is correct
21	Correct	101 ms	216864 KB	Output is correct
22	Correct	108 ms	218316 KB	Output is correct
23	Incorrect	92 ms	216400 KB	1st lines differ - on the 1st token, expected: '3061077668538', found: '3060654583637'
24	Halted	0 ms	0 KB	-

Subtask #7
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1090 ms	86192 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	1078 ms	95872 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Submission #627908

Compilation message