oj.uz

Submission #636811

# Submission time Handle Problem Language Result Execution time Memory
636811 2022-08-30T08:57:48 Z dsabolic Catfish Farm (IOI22_fish) C++17
0 / 100
 29 ms 12148 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 305;

ll dp[N][N][2][2];
int n, m;
vector<int> x;
vector<int> y;
vector<int> w;

int ima(int i, int j) {
	auto it = lower_bound(x.begin(), x.end(), i);
	if(it == x.end()) return 0;
	if(*it == i && y[it - x.begin()] == j) return w[it - x.begin()];
	else return 0;
}

ll solve(int i, int hp, bool f1, bool f2) {
	if(i == n) return 0;
	ll& ret = dp[i][hp][f1][f2];
	if(ret != -1) return ret;
	ret = 0;
	
	if(f2) {
		for(int h = 0; h <= n; ++h) {
			if(h == 0) {
				ret = max(ret, solve(i + 1, 0, 0, 1));
			} else {
				//ret = max(ret, solve(i + 1, 0, 0, 0) + ima(i - 1, h) + ima(i + 1, h));
				if(hp == h) ret = max(ret, solve(i + 1, h, 0, 0) + ima(i + 1, h));
				else ret = max(ret, solve(i + 1, h, 0, 0) + ima(i + 1, h) + ima(i - 1, h));
			}
		}
	} else {
		if(!f1) {
			for(int h = hp + 1; h <= n; ++h) {
				ret = max(ret, solve(i + 1, h, 0, 0) + ima(i - 1, h) + ima(i + 1, h));
			}
		}
		for(int h = hp; h >= 0; --h) {
			if(h == 0) {
				ret = max(ret, solve(i + 1, hp, 0, 1));
			} else {
				ret = max(ret, solve(i + 1, h, 1, 0) + ima(i + 1, h) - (h == hp) * ima(i, h));
			}
		}
	}
	
	return ret;
}

ll max_weights(int z, int d, vector<int> a, vector<int> b, vector<int> c) {
	memset(dp, -1, sizeof dp);
	x = a, y = b, w = c;
	n = z, m = d;
	return solve(0, 0, 0, 0);
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 12148 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3156 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 6356 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3156 KB 1st lines differ - on the 1st token, expected: '3', found: '1'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3156 KB 1st lines differ - on the 1st token, expected: '3', found: '1'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3156 KB 1st lines differ - on the 1st token, expected: '3', found: '1'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 6356 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 12148 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -