답안 #627903

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
627903	2022-08-13T00:49:12 Z	jwvg0425	메기 농장 (IOI22_fish)	C++17	14 / 100	1000 ms	218384 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;
		}

		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

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1049 ms	82516 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	100 ms	212268 KB	Output is correct
2	Execution timed out	1078 ms	89468 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #3
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1072 ms	86612 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	97 ms	212384 KB	Output is correct
2	Correct	83 ms	212312 KB	Output is correct
3	Correct	80 ms	212264 KB	Output is correct
4	Correct	86 ms	212300 KB	Output is correct
5	Correct	79 ms	212244 KB	Output is correct
6	Correct	85 ms	212312 KB	Output is correct
7	Correct	94 ms	212364 KB	Output is correct
8	Correct	81 ms	212300 KB	Output is correct
9	Correct	87 ms	213712 KB	Output is correct
10	Correct	87 ms	215568 KB	Output is correct
11	Correct	85 ms	213788 KB	Output is correct
12	Correct	101 ms	215504 KB	Output is correct
13	Correct	83 ms	212924 KB	Output is correct
14	Correct	93 ms	215520 KB	Output is correct

Subtask #5
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	97 ms	212384 KB	Output is correct
2	Correct	83 ms	212312 KB	Output is correct
3	Correct	80 ms	212264 KB	Output is correct
4	Correct	86 ms	212300 KB	Output is correct
5	Correct	79 ms	212244 KB	Output is correct
6	Correct	85 ms	212312 KB	Output is correct
7	Correct	94 ms	212364 KB	Output is correct
8	Correct	81 ms	212300 KB	Output is correct
9	Correct	87 ms	213712 KB	Output is correct
10	Correct	87 ms	215568 KB	Output is correct
11	Correct	85 ms	213788 KB	Output is correct
12	Correct	101 ms	215504 KB	Output is correct
13	Correct	83 ms	212924 KB	Output is correct
14	Correct	93 ms	215520 KB	Output is correct
15	Correct	89 ms	215552 KB	Output is correct
16	Correct	86 ms	212852 KB	Output is correct
17	Correct	104 ms	216612 KB	Output is correct
18	Correct	98 ms	216412 KB	Output is correct
19	Correct	107 ms	216948 KB	Output is correct
20	Correct	118 ms	216928 KB	Output is correct
21	Correct	98 ms	216888 KB	Output is correct
22	Correct	112 ms	218384 KB	Output is correct
23	Incorrect	93 ms	216356 KB	1st lines differ - on the 1st token, expected: '3061077668538', found: '3060654583637'
24	Halted	0 ms	0 KB	-

Subtask #6
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	97 ms	212384 KB	Output is correct
2	Correct	83 ms	212312 KB	Output is correct
3	Correct	80 ms	212264 KB	Output is correct
4	Correct	86 ms	212300 KB	Output is correct
5	Correct	79 ms	212244 KB	Output is correct
6	Correct	85 ms	212312 KB	Output is correct
7	Correct	94 ms	212364 KB	Output is correct
8	Correct	81 ms	212300 KB	Output is correct
9	Correct	87 ms	213712 KB	Output is correct
10	Correct	87 ms	215568 KB	Output is correct
11	Correct	85 ms	213788 KB	Output is correct
12	Correct	101 ms	215504 KB	Output is correct
13	Correct	83 ms	212924 KB	Output is correct
14	Correct	93 ms	215520 KB	Output is correct
15	Correct	89 ms	215552 KB	Output is correct
16	Correct	86 ms	212852 KB	Output is correct
17	Correct	104 ms	216612 KB	Output is correct
18	Correct	98 ms	216412 KB	Output is correct
19	Correct	107 ms	216948 KB	Output is correct
20	Correct	118 ms	216928 KB	Output is correct
21	Correct	98 ms	216888 KB	Output is correct
22	Correct	112 ms	218384 KB	Output is correct
23	Incorrect	93 ms	216356 KB	1st lines differ - on the 1st token, expected: '3061077668538', found: '3060654583637'
24	Halted	0 ms	0 KB	-

Subtask #7
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1072 ms	86612 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1049 ms	82516 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

답안 #627903

Compilation message