oj.uz

답안 #1005078

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1005078 2024-06-22T06:59:45 Z alex_2008 메기 농장 (IOI22_fish) C++17
0 / 100
 26 ms 4700 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(r2, c) - f(r1 - 1, c);
}
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 - 1][j];
		}
	}
	//H bardzrutyun => (0, 1, ..., H - 1) bolory vercvac en
	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]);
			}
		}
	}
	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() {
	cout << max_weights(5, 4, { 0, 1, 4, 3 }, { 2, 1, 4, 3 }, { 5, 2, 1, 3 });
}
*/

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 26 ms 4700 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2392 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 14 ms 1116 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 2652 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 2652 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 2652 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 26 ms 4700 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -