oj.uz

Submission #1005167

# Submission time Handle Problem Language Result Execution time Memory
1005167 2024-06-22T08:21:36 Z alex_2008 Catfish Farm (IOI22_fish) C++17
35 / 100
 297 ms 894356 KB 
#include "fish.h"
#include <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAX_N = 3e2 + 10;
ll col_sm[MAX_N][MAX_N];
ll dp[MAX_N][MAX_N][MAX_N];
ll dp_pref[MAX_N][MAX_N][MAX_N];
ll dp_suff[MAX_N][MAX_N][MAX_N];
ll pref_mx[MAX_N][MAX_N][MAX_N];
ll dpp[MAX_N][MAX_N][MAX_N];
ll f(int r, int c) {
	if (r == -1) return 0;
	return col_sm[r][c];
}
ll sm(int c, int r1, int r2) {
	return f(c, r2) - f(c, r1 - 1);
}
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
	for (int i = 0; i < M; i++) {
		col_sm[X[i]][Y[i]] = W[i];
	}
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= N; j++) {
			col_sm[i][j] += col_sm[i][j - 1];
		}
	}
	//H bardzrutyun => (0, 1, ..., H - 1) bolory vercvac en
	for (int h1 = 0; h1 <= N; h1++) {
		for (int h2 = 0; h2 <= N; h2++) {
			if (h1 >= h2) dp[1][h1][h2] = sm(1, h2, h1 - 1);
			else dp[1][h1][h2] = sm(0, h1, h2 - 1);
			
		}
	}
	//cout << 0 << " " << 0 << " " << 5 << " " << sm(0, 0, 4) << " " << col_sm[0][4] << "\n";
	for (int h1 = 0; h1 <= N; h1++) {
		for (int h2 = 0; h2 <= N; h2++) {
			pref_mx[1][h1][h2] = max(dp[1][h1][h2], pref_mx[1][h1 - 1][h2]);
			if (h1 >= h2) {
				dp_pref[1][h1][h2] = max(dp_pref[1][h1 - 1][h2], dp[1][h1][h2] - sm(1, h2, h1 - 1));
			}
		}
	}
	for (int h1 = N; h1 >= 0; h1--) {
		for (int h2 = 0; h2 <= h1; h2++) {
			dp_suff[1][h1][h2] = max(dp[1][h1][h2], dp_suff[1][h1 + 1][h2]);
		}
	}
	for (int i = 2; i < N; i++) {
		for (int h1 = 0; h1 <= N; h1++) {
			for (int h2 = 0; h2 <= N; h2++) {
				if (h1 >= h2) {
					//dp[i][h1][h2] = max(dp[i - 1][esim][h1] + sm(i, h2, h1 - 1));
					dp[i][h1][h2] = pref_mx[i - 1][N][h1] + sm(i, h2, h1 - 1);
				}
				else {
					//h1 < h2
					//if h3 <= h1 < h2
					dp[i][h1][h2] = pref_mx[i - 1][h1][h1] + sm(i - 1, h1, h2 - 1);
					//if h1 < h2 <= h3
					//dp[i][h1][h2] = max(dp[i - 1][h3][h1] - sm(i, h1, h2 - 1))
					dp[i][h1][h2] = max(dp[i][h1][h2], dp_suff[i - 1][h2][h1]);
					//if h1 < h3 <= h2
					dp[i][h1][h2] = max(dp[i][h1][h2], dp_pref[i - 1][h2][h1] + sm(i - 1, h1, h2 - 1));
				}
			}
		}
		for (int h1 = 0; h1 <= N; h1++) {
			for (int h2 = 0; h2 <= N; h2++) {
				pref_mx[i][h1][h2] = max(dp[i][h1][h2], pref_mx[i][h1 - 1][h2]);
				if (h1 >= h2) {
					dp_pref[i][h1][h2] = max(dp_pref[i][h1 - 1][h2], dp[i][h1][h2] - sm(i, h2, h1 - 1));
				}
			}
		}
		for (int h1 = N; h1 >= 0; h1--) {
			for (int h2 = 0; h2 <= h1; h2++) {
				dp_suff[i][h1][h2] = max(dp[i][h1][h2], dp_suff[i][h1 + 1][h2]);
			}
		}
	}
	//cout << "? " << dp[2][3][3] << "\n";
	ll mx = 0;
	for (int h1 = 0; h1 <= N; h1++) {
		for (int h2 = 0; h2 <= N; h2++) {
			mx = max(mx, dp[N - 1][h1][h2]);
		}
	}
	return mx;
}
/*
int main() {
	//3 2
	//0 0 1
	//1 1 1
	//cout << max_weights(3, 2, { 0, 1 }, { 0, 1 }, { 1, 1 });
	
}
*/

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Runtime error 45 ms 7880 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 0 ms 2500 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 68 ms 335564 KB Output is correct
10 Correct 259 ms 890708 KB Output is correct
11 Correct 69 ms 335440 KB Output is correct
12 Correct 277 ms 890704 KB Output is correct
13 Correct 22 ms 122204 KB Output is correct
14 Correct 255 ms 890704 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 0 ms 2500 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 68 ms 335564 KB Output is correct
10 Correct 259 ms 890708 KB Output is correct
11 Correct 69 ms 335440 KB Output is correct
12 Correct 277 ms 890704 KB Output is correct
13 Correct 22 ms 122204 KB Output is correct
14 Correct 255 ms 890704 KB Output is correct
15 Correct 281 ms 890960 KB Output is correct
16 Correct 24 ms 122200 KB Output is correct
17 Correct 279 ms 892636 KB Output is correct
18 Correct 297 ms 892464 KB Output is correct
19 Correct 256 ms 892500 KB Output is correct
20 Correct 245 ms 892460 KB Output is correct
21 Correct 261 ms 892756 KB Output is correct
22 Correct 262 ms 894356 KB Output is correct
23 Correct 256 ms 891028 KB Output is correct
24 Correct 261 ms 892036 KB Output is correct
25 Correct 263 ms 890704 KB Output is correct
26 Correct 267 ms 891136 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 0 ms 2500 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 68 ms 335564 KB Output is correct
10 Correct 259 ms 890708 KB Output is correct
11 Correct 69 ms 335440 KB Output is correct
12 Correct 277 ms 890704 KB Output is correct
13 Correct 22 ms 122204 KB Output is correct
14 Correct 255 ms 890704 KB Output is correct
15 Correct 281 ms 890960 KB Output is correct
16 Correct 24 ms 122200 KB Output is correct
17 Correct 279 ms 892636 KB Output is correct
18 Correct 297 ms 892464 KB Output is correct
19 Correct 256 ms 892500 KB Output is correct
20 Correct 245 ms 892460 KB Output is correct
21 Correct 261 ms 892756 KB Output is correct
22 Correct 262 ms 894356 KB Output is correct
23 Correct 256 ms 891028 KB Output is correct
24 Correct 261 ms 892036 KB Output is correct
25 Correct 263 ms 890704 KB Output is correct
26 Correct 267 ms 891136 KB Output is correct
27 Runtime error 15 ms 600 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 1116 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 30 ms 4188 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -