oj.uz

답안 #1055939

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1055939 2024-08-13T06:42:21 Z pawned 메기 농장 (IOI22_fish) C++17
0 / 100
 1000 ms 14820 KB 
#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;

#include "fish.h"

int MAX_R = 10;
int MAX_C = 10;

ll max_weights(int N, int M, vector<int> X_g, vector<int> Y_g, vector<int> W_g) {
	MAX_R = min(N, 3);
	MAX_C = N;
	vector<vi> a(MAX_R, vi(MAX_C, 0));
	for (int i = 0; i < M; i++) {
		if (X_g[i] < MAX_R && Y_g[i] < MAX_C)
			a[X_g[i]][Y_g[i]] += W_g[i];
	}
/*	cout<<"a: "<<endl;
	for (vi v : a) {
		for (ll x : v)
			cout<<x<<" ";
		cout<<endl;
	}*/
	vector<vi> pfs(MAX_R, vi(MAX_C + 1, 0));	// vertical pfs
	for (int i = 0; i < MAX_R; i++) {
		pfs[i][0] = 0;
		for (int j = 1; j <= MAX_C; j++) {
			pfs[i][j] = pfs[i][j - 1] + a[i][j - 1];
		}
	}
/*	cout<<"pfs: "<<endl;
	for (vi v : pfs) {
		for (ll x : v)
			cout<<x<<" ";
		cout<<endl;
	}*/
	vector<vi> dp(MAX_R + 1, vi(MAX_C + 1, 0));
	// dp[i][j]: max sum till i, exclusive; j = pier height
	// prefix max / sum to optimize?
	for (int i = 1; i <= MAX_C; i++) {
		dp[0][i] = -1e18;
	}
	for (int i = 1; i <= MAX_R; i++) {
		// a[i - 1] is empty
		for (int j = 0; j <= MAX_C; j++) {
			dp[i][0] = max(dp[i][0], dp[i - 1][j] + (pfs[i - 1][j] - pfs[i - 1][0]));
		}
		for (int j = 1; j <= MAX_C; j++) {	// fill up to j
			// try all right filled combinations
			if (i == 1) {	// first coln
				dp[i][j] = 0;
			}
			else if (i == 2) {
				for (int k = 0; k <= j; k++) {	// left is up to k <= j
					dp[i][j] = max(dp[i][j], dp[i - 1][k] + (pfs[i - 2][j] - pfs[i - 2][k]));
				}
				for (int k = j + 1; k <= MAX_C; k++) {	// left is up to k > j
					dp[i][j] = max(dp[i][j], dp[i - 1][k] + (pfs[i - 1][k] - pfs[i - 1][j]));
				}
			}
			else {	// i >= 3
				for (int k = 0; k <= j; k++) {	// left is up to k <= j
					for (int l = 0; l <= MAX_C; l++) {	// 2x left is up to l
						if (l >= j) {	// nothing added
							dp[i][j] = max(dp[i][j], dp[i - 2][l] + (pfs[i - 2][l] - pfs[i - 2][k]));
						}
						else if (l >= k) {
							dp[i][j] = max(dp[i][j], dp[i - 2][l] + (pfs[i - 2][j] - pfs[i - 2][k]));
						}
						else {
							dp[i][j] = max(dp[i][j], dp[i - 2][l] + (pfs[i - 3][k] - pfs[i - 3][l]) + (pfs[i - 2][j] - pfs[i - 2][k]));
						}
					}
				}
				for (int k = j + 1; k <= MAX_C; k++) {	// left is up to k > j
					dp[i][j] = max(dp[i][j], dp[i - 1][k] + (pfs[i - 1][k] - pfs[i - 1][j]));
				}
			}
		}
	}
/*	cout<<"dp: "<<endl;
	for (vi v : dp) {
		for (ll x : v)
			cout<<x<<" ";
		cout<<endl;
	}*/
	ll ans = 0;
	for (int i = 0; i <= MAX_C; i++) {
		ans = max(ans, dp[MAX_R][i]);
	}
	return ans;
}

// can extend subtask 3 logic for polynomial soln
// optimize with segtree range max if needed

// if have poly soln, can get subtasks 2 and 4 right away by changing bounds

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1068 ms 9884 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Execution timed out 1091 ms 14820 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1078 ms 9036 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 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 348 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 348 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 Execution timed out 1078 ms 9036 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1068 ms 9884 KB Time limit exceeded
2 Halted 0 ms 0 KB -