oj.uz

Submission #1056610

# Submission time Handle Problem Language Result Execution time Memory
1056610 2024-08-13T10:18:29 Z pawned Catfish Farm (IOI22_fish) C++17
14 / 100
 708 ms 2097152 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_H = 15;

ll max_weights(int N, int M, vector<int> X_g, vector<int> Y_g, vector<int> W_g) {
	MAX_H = min(MAX_H, N);
	// precompute all range increasing / decreasing
	vector<vi> a(N, vi(N, 0));
	for (int i = 0; i < M; i++) {
		a[X_g[i]][Y_g[i]] += W_g[i];
	}
	vector<vi> pfs(N, vi(N + 1, 0));
	for (int i = 0; i < N; i++) {
		for (int j = 1; j <= N; j++) {
			pfs[i][j] = pfs[i][j - 1] + a[i][j - 1];
		}
	}
/*	cout<<"a: "<<endl;
	for (vi v : a) {
		for (int x : v)
			cout<<x<<" ";
		cout<<endl;
	}*/
	vector<vector<vi>> inc(N, vector<vi>(N, vi(MAX_H + 1, 0)));
	// inc[i][j][k] (i < j): max sum of going up on [i, j]
	// only considering [0, k - 1]
	vector<vector<vi>> dec(N, vector<vi>(N, vi(MAX_H + 1, 0)));
	// dec[i][j][k] (i < j): max sum of going down on [i, j]
	// only considering [k, MAX_H - 1]
	for (int i = 0; i < N; i++) {	// left pos
		// compute for [i, i]
		inc[i][i][0] = 0;
		dec[i][i][MAX_H] = 0;
		for (int j = 1; j <= MAX_H; j++) {
			inc[i][i][j] = inc[i][i][j - 1] + a[i][j - 1];
		}
		for (int j = MAX_H - 1; j >= 0; j--) {
			dec[i][i][j] = dec[i][i][j + 1] + a[i][j];
		}
		for (int j = i + 1; j < N; j++) {	// [i, j], inclusive
			for (int k = 0; k <= MAX_H; k++) {	// min / max height is k
				for (int l = 0; l <= k; l++) {	// increasing
					// use [l, k-1] for new coln
					inc[i][j][k] = max(inc[i][j][k], inc[i][j - 1][l] + (pfs[j][k] - pfs[j][l]));
				}
				for (int l = k; l <= MAX_H; l++) {	// decreasing
					// use [k, l-1] for new coln
					dec[i][j][k] = max(dec[i][j][k], dec[i][j - 1][l] + (pfs[j][l] - pfs[j][k]));
				}
			}
		}
	}
	vector<vi> incr(N, vi(N, 0));
	vector<vi> decr(N, vi(N, 0));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			incr[i][j] = inc[i][j][MAX_H];
			decr[i][j] = dec[i][j][0];
		}
	}
/*	cout<<"incr: "<<endl;
	for (vi v : incr) {
		for (ll x : v)
			cout<<x<<" ";
		cout<<endl;
	}
	cout<<"decr: "<<endl;
	for (vi v : decr) {
		for (ll x : v)
			cout<<x<<" ";
		cout<<endl;
	}*/

	vector<vi> dp(N, vi(2, 0));
	// dp[i][j]: maximum sum until i (exclusive) given last coln type j
	// j = 0: increasing ended; j = 1: decreasing ended
	// only inc can follow dec without skip; rest all need skip
	// can only start w/ inc or blank
	// can only end w/ dec or blank
	dp[0][0] = incr[0][0];
	dp[0][1] = -1e18;
	for (int i = 1; i < N; i++) {
		// compute dp[i][0]
		dp[i][0] = incr[0][i];	// nothing else
		for (int j = 0; j < i; j++) {	// prev was decr
			// start new incr at j+1
			dp[i][0] = max(dp[i][0], dp[j][1] + incr[j + 1][i]);
		}
		for (int j = 1; j < i; j++) {	// prev was incr
			// need to skip j to start new incr at j+1
			dp[i][0] = max(dp[i][0], dp[j - 1][0] + incr[j + 1][i]);
		}
		// compute dp[i][1]
		dp[i][1] = decr[1][i];
		for (int j = 1; j < i; j++) {	// prev was incr
			dp[i][1] = max(dp[i][1], dp[j - 1][0] + decr[j + 1][i]);
		}
		for (int j = 1; j < i; j++) {	// prev was decr
			dp[i][1] = max(dp[i][1], dp[j - 1][1] + decr[j + 1][i]);
		}
	}
/*	cout<<"dp: "<<endl;
	for (int i = 0; i < N; i++) {
		cout<<dp[i][0]<<", "<<dp[i][1]<<endl;
	}*/
	ll ans = 0;
	for (int i = 0; i < N - 1; i++) {
		ans = max(ans, dp[i][0]);
	}
	for (int i = 1; i < N; i++) {
		ans = max(ans, dp[i][1]);
	}
	return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 674 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 708 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 637 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 648 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 6 ms 8504 KB Output is correct
10 Correct 24 ms 32860 KB Output is correct
11 Correct 6 ms 8536 KB Output is correct
12 Correct 24 ms 32860 KB Output is correct
13 Correct 2 ms 2392 KB Output is correct
14 Correct 25 ms 32832 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 648 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 6 ms 8504 KB Output is correct
10 Correct 24 ms 32860 KB Output is correct
11 Correct 6 ms 8536 KB Output is correct
12 Correct 24 ms 32860 KB Output is correct
13 Correct 2 ms 2392 KB Output is correct
14 Correct 25 ms 32832 KB Output is correct
15 Incorrect 22 ms 32860 KB 1st lines differ - on the 1st token, expected: '299', found: '15'
16 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 648 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 6 ms 8504 KB Output is correct
10 Correct 24 ms 32860 KB Output is correct
11 Correct 6 ms 8536 KB Output is correct
12 Correct 24 ms 32860 KB Output is correct
13 Correct 2 ms 2392 KB Output is correct
14 Correct 25 ms 32832 KB Output is correct
15 Incorrect 22 ms 32860 KB 1st lines differ - on the 1st token, expected: '299', found: '15'
16 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 637 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 674 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -