oj.uz

Submission #628058

# Submission time Handle Problem Language Result Execution time Memory
628058 2022-08-13T04:06:52 Z jwvg0425 Catfish Farm (IOI22_fish) C++17
44 / 100
 1000 ms 361536 KB 
#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 table2[100005][5][3];
i64 val[3005][3005];
i64 val2[100005][5];
i64 psum[3005][3005];
i64 psum2[100005][5];
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 dp2(int x, int y, int type)
{
	if (x >= n + 1)
		return 0;

	if (table2[x][y][type] != -1)
		return table2[x][y][type];

	auto& res = table2[x][y][type];
	res = 0;

	if (type == 2)
	{
		// 한 칸 더 위 or 오른쪽 위 or 두칸 뛰면서 desc
		if (y < 2)
		{
			res = max(res, val2[x][y] + dp2(x, y + 1, type));
			if (x < n - 1)
				res = max(res, val2[x][y] + dp2(x + 1, y + 1, type));
		}

		res = max({ res, val2[x][y] + dp2(x + 2, y, 1), val2[x][y] + dp2(x + 3, y, 1) });
	}
	else if (type == 1)
	{
		// 내 아래 다 먹고 여기부터 asc로 전환 가능
		if (x <= n - 1)
		{
			auto down = y == 0 ? 0 : psum2[x][y - 1];
			res = dp2(x, y, 2) + down;
		}

		// 그 외의 경우, 그냥 단순 내림차
		res = max(res, dp2(x, y, 0));
	}
	else
	{
		// 단순 내림차 -> 한칸 밑으로 or 오른쪽 한칸 밑으로
		if (y == 0)
		{
			// 맨밑 왔으면 그냥 한칸 옆으로 가면 됨
			res = dp2(x + 1, y, 1);
			return res;
		}

		if (x < n - 1 && y < 2)
			res = max(res, psum2[x][y] + dp2(x + 1, y + 1, 2));

		res = val2[x][y] + max({ dp2(x + 1, y - 1, 1), dp2(x, y - 1, 0), psum2[x][y - 1] + dp2(x + 2, y, 1), psum2[x][y - 1] + dp2(x + 3, y, 1) });
	}

	return res;
}

i64 sub3(int m, vector<int> x, vector<int> y, vector<int> w)
{
	for (int i = 0; i < m; i++)
		val2[x[i] + 1][y[i] + 1] += w[i];

	for (int x = 1; x <= n; x++)
		for (int y = 1; y <= n; y++)
			psum2[x][y] += psum2[x][y - 1] + val2[x][y];

	memset(table2, -1, sizeof(table2));

	return dp2(0, 0, 1);
}

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, y, 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

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2384 KB Output is correct
2 Correct 29 ms 3020 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 91 ms 8436 KB Output is correct
6 Correct 103 ms 8448 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1748 KB Output is correct
2 Correct 53 ms 7584 KB Output is correct
3 Correct 61 ms 8808 KB Output is correct
4 Correct 29 ms 2408 KB Output is correct
5 Correct 28 ms 3012 KB Output is correct
6 Correct 1 ms 1748 KB Output is correct
7 Correct 2 ms 1748 KB Output is correct
8 Correct 1 ms 1748 KB Output is correct
9 Correct 2 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 38 ms 4712 KB Output is correct
13 Correct 29 ms 5320 KB Output is correct
14 Correct 24 ms 4692 KB Output is correct
15 Correct 39 ms 4968 KB Output is correct
16 Correct 36 ms 4636 KB Output is correct
17 Correct 37 ms 4940 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 212276 KB Output is correct
2 Correct 81 ms 212376 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 81 ms 212304 KB Output is correct
9 Correct 84 ms 213732 KB Output is correct
10 Correct 93 ms 215744 KB Output is correct
11 Correct 89 ms 213768 KB Output is correct
12 Correct 89 ms 215548 KB Output is correct
13 Correct 107 ms 212912 KB Output is correct
14 Correct 96 ms 215568 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 212276 KB Output is correct
2 Correct 81 ms 212376 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 81 ms 212304 KB Output is correct
9 Correct 84 ms 213732 KB Output is correct
10 Correct 93 ms 215744 KB Output is correct
11 Correct 89 ms 213768 KB Output is correct
12 Correct 89 ms 215548 KB Output is correct
13 Correct 107 ms 212912 KB Output is correct
14 Correct 96 ms 215568 KB Output is correct
15 Correct 95 ms 215508 KB Output is correct
16 Correct 80 ms 212844 KB Output is correct
17 Correct 99 ms 216628 KB Output is correct
18 Correct 125 ms 216576 KB Output is correct
19 Correct 121 ms 216916 KB Output is correct
20 Correct 106 ms 216940 KB Output is correct
21 Correct 99 ms 216928 KB Output is correct
22 Correct 134 ms 218396 KB Output is correct
23 Correct 90 ms 216320 KB Output is correct
24 Correct 105 ms 216948 KB Output is correct
25 Correct 106 ms 215500 KB Output is correct
26 Correct 101 ms 215968 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 212276 KB Output is correct
2 Correct 81 ms 212376 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 81 ms 212304 KB Output is correct
9 Correct 84 ms 213732 KB Output is correct
10 Correct 93 ms 215744 KB Output is correct
11 Correct 89 ms 213768 KB Output is correct
12 Correct 89 ms 215548 KB Output is correct
13 Correct 107 ms 212912 KB Output is correct
14 Correct 96 ms 215568 KB Output is correct
15 Correct 95 ms 215508 KB Output is correct
16 Correct 80 ms 212844 KB Output is correct
17 Correct 99 ms 216628 KB Output is correct
18 Correct 125 ms 216576 KB Output is correct
19 Correct 121 ms 216916 KB Output is correct
20 Correct 106 ms 216940 KB Output is correct
21 Correct 99 ms 216928 KB Output is correct
22 Correct 134 ms 218396 KB Output is correct
23 Correct 90 ms 216320 KB Output is correct
24 Correct 105 ms 216948 KB Output is correct
25 Correct 106 ms 215500 KB Output is correct
26 Correct 101 ms 215968 KB Output is correct
27 Correct 769 ms 296116 KB Output is correct
28 Correct 176 ms 228620 KB Output is correct
29 Correct 834 ms 294128 KB Output is correct
30 Correct 992 ms 337008 KB Output is correct
31 Correct 793 ms 337556 KB Output is correct
32 Correct 183 ms 228556 KB Output is correct
33 Correct 823 ms 361536 KB Output is correct
34 Correct 804 ms 361448 KB Output is correct
35 Correct 768 ms 301660 KB Output is correct
36 Execution timed out 1012 ms 307428 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

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

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2384 KB Output is correct
2 Correct 29 ms 3020 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 91 ms 8436 KB Output is correct
6 Correct 103 ms 8448 KB Output is correct
7 Correct 2 ms 1748 KB Output is correct
8 Correct 53 ms 7584 KB Output is correct
9 Correct 61 ms 8808 KB Output is correct
10 Correct 29 ms 2408 KB Output is correct
11 Correct 28 ms 3012 KB Output is correct
12 Correct 1 ms 1748 KB Output is correct
13 Correct 2 ms 1748 KB Output is correct
14 Correct 1 ms 1748 KB Output is correct
15 Correct 2 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 38 ms 4712 KB Output is correct
19 Correct 29 ms 5320 KB Output is correct
20 Correct 24 ms 4692 KB Output is correct
21 Correct 39 ms 4968 KB Output is correct
22 Correct 36 ms 4636 KB Output is correct
23 Correct 37 ms 4940 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Execution timed out 1088 ms 1248 KB Time limit exceeded
26 Halted 0 ms 0 KB -