Submission #627891

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
627891	2022-08-13T00:41:17 Z	jwvg0425	Catfish Farm (IOI22_fish)	C++17	14 / 100	1000 ms	218476 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));
	}
	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, 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	1049 ms	102480 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	76 ms	212420 KB	Output is correct
2	Execution timed out	1090 ms	105108 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	1096 ms	95800 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	78 ms	212264 KB	Output is correct
2	Correct	77 ms	212316 KB	Output is correct
3	Correct	80 ms	212320 KB	Output is correct
4	Correct	77 ms	212356 KB	Output is correct
5	Correct	77 ms	212300 KB	Output is correct
6	Correct	84 ms	212316 KB	Output is correct
7	Correct	77 ms	212364 KB	Output is correct
8	Correct	76 ms	212320 KB	Output is correct
9	Correct	81 ms	213824 KB	Output is correct
10	Correct	84 ms	215524 KB	Output is correct
11	Correct	79 ms	213768 KB	Output is correct
12	Correct	83 ms	215580 KB	Output is correct
13	Correct	83 ms	212940 KB	Output is correct
14	Correct	85 ms	215580 KB	Output is correct

Subtask #5
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	78 ms	212264 KB	Output is correct
2	Correct	77 ms	212316 KB	Output is correct
3	Correct	80 ms	212320 KB	Output is correct
4	Correct	77 ms	212356 KB	Output is correct
5	Correct	77 ms	212300 KB	Output is correct
6	Correct	84 ms	212316 KB	Output is correct
7	Correct	77 ms	212364 KB	Output is correct
8	Correct	76 ms	212320 KB	Output is correct
9	Correct	81 ms	213824 KB	Output is correct
10	Correct	84 ms	215524 KB	Output is correct
11	Correct	79 ms	213768 KB	Output is correct
12	Correct	83 ms	215580 KB	Output is correct
13	Correct	83 ms	212940 KB	Output is correct
14	Correct	85 ms	215580 KB	Output is correct
15	Correct	105 ms	215608 KB	Output is correct
16	Correct	94 ms	212940 KB	Output is correct
17	Correct	99 ms	216652 KB	Output is correct
18	Correct	101 ms	216376 KB	Output is correct
19	Correct	125 ms	216880 KB	Output is correct
20	Correct	94 ms	217000 KB	Output is correct
21	Correct	95 ms	216980 KB	Output is correct
22	Correct	147 ms	218476 KB	Output is correct
23	Incorrect	85 ms	216396 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	78 ms	212264 KB	Output is correct
2	Correct	77 ms	212316 KB	Output is correct
3	Correct	80 ms	212320 KB	Output is correct
4	Correct	77 ms	212356 KB	Output is correct
5	Correct	77 ms	212300 KB	Output is correct
6	Correct	84 ms	212316 KB	Output is correct
7	Correct	77 ms	212364 KB	Output is correct
8	Correct	76 ms	212320 KB	Output is correct
9	Correct	81 ms	213824 KB	Output is correct
10	Correct	84 ms	215524 KB	Output is correct
11	Correct	79 ms	213768 KB	Output is correct
12	Correct	83 ms	215580 KB	Output is correct
13	Correct	83 ms	212940 KB	Output is correct
14	Correct	85 ms	215580 KB	Output is correct
15	Correct	105 ms	215608 KB	Output is correct
16	Correct	94 ms	212940 KB	Output is correct
17	Correct	99 ms	216652 KB	Output is correct
18	Correct	101 ms	216376 KB	Output is correct
19	Correct	125 ms	216880 KB	Output is correct
20	Correct	94 ms	217000 KB	Output is correct
21	Correct	95 ms	216980 KB	Output is correct
22	Correct	147 ms	218476 KB	Output is correct
23	Incorrect	85 ms	216396 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	1096 ms	95800 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	1049 ms	102480 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Submission #627891

Compilation message