답안 #628052

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
628052	2022-08-13T04:01:45 Z	jwvg0425	메기 농장 (IOI22_fish)	C++17	61 / 100	720 ms	361628 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 sub3(int m, vector<int> x, vector<int> w)
{
	vector<i64> arr(n);
	for (int i = 0; i < m; i++)
		arr[x[i]] = w[i];

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

	table[0][0] = arr[0];

	i64 ans = arr[0];

	for (int i = 1; i < n; i++)
	{
		if (i >= 2)
			table[i][0] = arr[i] + max(table[i - 2][0], table[i - 2][1]);
		else
			table[i][0] = arr[i];

		table[i][1] = arr[i] + table[i - 1][0];

		ans = max({ ans, table[i][0], table[i][1] });
	}

	return ans;
}

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);

	if (all_of(all(y), [](int yi) { return yi == 0; }))
		return sub3(m, x, 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

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	2416 KB	Output is correct
2	Correct	27 ms	3032 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	82 ms	8436 KB	Output is correct
6	Correct	81 ms	8424 KB	Output is correct

Subtask #2
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1748 KB	Output is correct
2	Correct	45 ms	7596 KB	Output is correct
3	Correct	56 ms	8924 KB	Output is correct
4	Correct	26 ms	2416 KB	Output is correct
5	Correct	27 ms	3016 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	0 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	25 ms	4720 KB	Output is correct
13	Correct	27 ms	5336 KB	Output is correct
14	Correct	23 ms	4728 KB	Output is correct
15	Correct	27 ms	4948 KB	Output is correct
16	Correct	23 ms	4728 KB	Output is correct
17	Correct	26 ms	4956 KB	Output is correct

Subtask #3
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	2644 KB	Output is correct
3	Incorrect	15 ms	4156 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '21050164171924'
4	Halted	0 ms	0 KB	-

Subtask #4
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	77 ms	212420 KB	Output is correct
2	Correct	82 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	1748 KB	Output is correct
6	Correct	1 ms	1748 KB	Output is correct
7	Correct	1 ms	1748 KB	Output is correct
8	Correct	76 ms	212348 KB	Output is correct
9	Correct	81 ms	213708 KB	Output is correct
10	Correct	84 ms	215584 KB	Output is correct
11	Correct	83 ms	213744 KB	Output is correct
12	Correct	84 ms	215500 KB	Output is correct
13	Correct	79 ms	213024 KB	Output is correct
14	Correct	91 ms	215504 KB	Output is correct

Subtask #5
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	77 ms	212420 KB	Output is correct
2	Correct	82 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	1748 KB	Output is correct
6	Correct	1 ms	1748 KB	Output is correct
7	Correct	1 ms	1748 KB	Output is correct
8	Correct	76 ms	212348 KB	Output is correct
9	Correct	81 ms	213708 KB	Output is correct
10	Correct	84 ms	215584 KB	Output is correct
11	Correct	83 ms	213744 KB	Output is correct
12	Correct	84 ms	215500 KB	Output is correct
13	Correct	79 ms	213024 KB	Output is correct
14	Correct	91 ms	215504 KB	Output is correct
15	Correct	86 ms	215508 KB	Output is correct
16	Correct	79 ms	212832 KB	Output is correct
17	Correct	97 ms	216604 KB	Output is correct
18	Correct	119 ms	216488 KB	Output is correct
19	Correct	96 ms	216924 KB	Output is correct
20	Correct	98 ms	217012 KB	Output is correct
21	Correct	97 ms	217036 KB	Output is correct
22	Correct	106 ms	218392 KB	Output is correct
23	Correct	89 ms	216320 KB	Output is correct
24	Correct	92 ms	216932 KB	Output is correct
25	Correct	88 ms	215644 KB	Output is correct
26	Correct	90 ms	215936 KB	Output is correct

Subtask #6
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	77 ms	212420 KB	Output is correct
2	Correct	82 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	1748 KB	Output is correct
6	Correct	1 ms	1748 KB	Output is correct
7	Correct	1 ms	1748 KB	Output is correct
8	Correct	76 ms	212348 KB	Output is correct
9	Correct	81 ms	213708 KB	Output is correct
10	Correct	84 ms	215584 KB	Output is correct
11	Correct	83 ms	213744 KB	Output is correct
12	Correct	84 ms	215500 KB	Output is correct
13	Correct	79 ms	213024 KB	Output is correct
14	Correct	91 ms	215504 KB	Output is correct
15	Correct	86 ms	215508 KB	Output is correct
16	Correct	79 ms	212832 KB	Output is correct
17	Correct	97 ms	216604 KB	Output is correct
18	Correct	119 ms	216488 KB	Output is correct
19	Correct	96 ms	216924 KB	Output is correct
20	Correct	98 ms	217012 KB	Output is correct
21	Correct	97 ms	217036 KB	Output is correct
22	Correct	106 ms	218392 KB	Output is correct
23	Correct	89 ms	216320 KB	Output is correct
24	Correct	92 ms	216932 KB	Output is correct
25	Correct	88 ms	215644 KB	Output is correct
26	Correct	90 ms	215936 KB	Output is correct
27	Correct	629 ms	296092 KB	Output is correct
28	Correct	168 ms	228736 KB	Output is correct
29	Correct	701 ms	294124 KB	Output is correct
30	Correct	720 ms	336976 KB	Output is correct
31	Correct	718 ms	337672 KB	Output is correct
32	Correct	176 ms	228584 KB	Output is correct
33	Correct	713 ms	361628 KB	Output is correct
34	Correct	717 ms	361536 KB	Output is correct
35	Correct	664 ms	301568 KB	Output is correct
36	Correct	717 ms	307292 KB	Output is correct

Subtask #7
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	2644 KB	Output is correct
3	Incorrect	15 ms	4156 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '21050164171924'
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	2416 KB	Output is correct
2	Correct	27 ms	3032 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	82 ms	8436 KB	Output is correct
6	Correct	81 ms	8424 KB	Output is correct
7	Correct	1 ms	1748 KB	Output is correct
8	Correct	45 ms	7596 KB	Output is correct
9	Correct	56 ms	8924 KB	Output is correct
10	Correct	26 ms	2416 KB	Output is correct
11	Correct	27 ms	3016 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	0 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	25 ms	4720 KB	Output is correct
19	Correct	27 ms	5336 KB	Output is correct
20	Correct	23 ms	4728 KB	Output is correct
21	Correct	27 ms	4948 KB	Output is correct
22	Correct	23 ms	4728 KB	Output is correct
23	Correct	26 ms	4956 KB	Output is correct
24	Correct	0 ms	212 KB	Output is correct
25	Correct	1 ms	2644 KB	Output is correct
26	Incorrect	15 ms	4156 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '21050164171924'
27	Halted	0 ms	0 KB	-

답안 #628052

Compilation message