oj.uz

Submission #632529

# Submission time Handle Problem Language Result Execution time Memory
632529 2022-08-20T09:50:06 Z Red_Inside Catfish Farm (IOI22_fish) C++17
52 / 100
 1000 ms 577524 KB 
#include "fish.h"
//
#include <bits/stdc++.h>

#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define o cout<<"BUG"<<endl;
#define FOR(i, j, n) for(int j = i; j < n; ++j)
#define forn(i, j, n) for(int j = i; j <= n; ++j)
#define nfor(i, j, n) for(int j = n; j >= i; --j)
#define all(v) v.begin(), v.end()
#define ld long double
#define ull unsigned long long

using namespace std;
const int maxn=5000+100,LOG=20,mod=998244353;
int block = 106, timer = 0;
const ld EPS = 1e-18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define bt(i) (1 << (i))
//#define int ll
const ll inf=2e18;
#define y1 yy
#define prev pre
#define pii pair <int, int>

ll n, a[maxn][maxn], dp[maxn][maxn][2], dp1[maxn], dp2[maxn];
ll pref[maxn][maxn], prefdp[maxn][maxn], prefdp2[maxn][maxn], suffdp[maxn][maxn];

ll max_weights(int N, int m, vector <int> x, vector <int> y, vector <int> c)
{
	n = N;
	forn(0, i, m-1)
	{
		a[x[i]+1][y[i]+1] = c[i];
	}
	forn(1, i, n)
	{
		forn(1, j, n)
		{
			pref[i][j] = pref[i][j-1] + a[i][j];
		}
	}
	forn(1, j, n)
	{
		dp[1][j][0] = 0;
		dp[1][j][1] = -inf;
	}
	dp1[1] = 0;
	dp2[1] = 0;
	forn(1, j, n)
	{
		dp[0][j][0] = -inf;
		dp[0][j][1] = -inf;
	}
	suffdp[1][n + 1] = -inf;
	nfor(1, j, n)
	{
		suffdp[1][j] = max(max(dp[1][j][1], dp[1][j][0]) + pref[1+1][j], 
		suffdp[1][j + 1]);
	}
	prefdp[1][0] = -inf;
	prefdp2[1][0] = -inf;
	forn(1, j, n)
	{
		prefdp2[1][j] = max(prefdp2[1][j - 1], dp[1][j][0] - pref[1][j]);
		prefdp[1][j] = max(prefdp[1][j-1], max(dp[1][j][0], dp[1][j][1]));
	}
	prefdp[0][0] = -inf;
	forn(2, i, n)
	{
		dp1[i] = 0;
		forn(1, j, n)
		{
			dp[i][j][0] = dp2[i-1]+pref[i-1][j];
			dp[i][j][0] = max(dp[i][j][0], prefdp2[i-1][j-1] + pref[i-1][j]);
			dp[i][j][0] = max(dp[i][j][0], prefdp[i-2][j]+pref[i-1][j]);
			dp[i][j][0] = max(dp[i][j][0], suffdp[i-2][j+1]);
			dp[i][j][1] = -inf;
			dp[i][j][1] = max(dp[i][j][1], suffdp[i - 1][j + 1] - pref[i][j]);
			dp1[i] = max(dp1[i], max(dp[i-1][j][1], dp[i-1][j][0]) + pref[i][j]);
//			cout << i << " " << j << " " << dp[i][j][0] << " " << dp[i][j][1] << endl;
		}
		dp2[i] = max(dp2[i - 1], dp1[i - 1]);
		suffdp[i][n + 1] = -inf;
		nfor(1, j, n)
		{
			suffdp[i][j] = max(max(dp[i][j][1], dp[i][j][0]) + pref[i+1][j], 
			suffdp[i][j + 1]);
		}
		prefdp[i][0] = -inf;
		prefdp2[i][0] = -inf;
		forn(1, j, n)
		{
			prefdp2[i][j] = max(prefdp2[i][j - 1], dp[i][j][0] - pref[i][j]);
			prefdp[i][j] = max(prefdp[i][j-1], max(dp[i][j][0], dp[i][j][1]));
		}
		
	}
	ll ans = 0;
	forn(1, j, n)
	{
		ans = max(ans, dp[n][j][0]);
		ans = max(ans, dp[n][j][1]);
	}
	ans = max(ans, dp1[n]);
	ans = max(ans, dp2[n]);
	return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1095 ms 169060 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Execution timed out 1066 ms 162268 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1095 ms 147624 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 9 ms 11988 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 7 ms 11988 KB Output is correct
13 Correct 1 ms 2388 KB Output is correct
14 Correct 9 ms 11860 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 9 ms 11988 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 7 ms 11988 KB Output is correct
13 Correct 1 ms 2388 KB Output is correct
14 Correct 9 ms 11860 KB Output is correct
15 Correct 8 ms 11860 KB Output is correct
16 Correct 3 ms 2260 KB Output is correct
17 Correct 20 ms 13628 KB Output is correct
18 Correct 18 ms 13524 KB Output is correct
19 Correct 19 ms 13920 KB Output is correct
20 Correct 25 ms 13908 KB Output is correct
21 Correct 20 ms 13848 KB Output is correct
22 Correct 31 ms 16064 KB Output is correct
23 Correct 11 ms 12860 KB Output is correct
24 Correct 16 ms 13652 KB Output is correct
25 Correct 7 ms 11988 KB Output is correct
26 Correct 9 ms 12372 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 9 ms 11988 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 7 ms 11988 KB Output is correct
13 Correct 1 ms 2388 KB Output is correct
14 Correct 9 ms 11860 KB Output is correct
15 Correct 8 ms 11860 KB Output is correct
16 Correct 3 ms 2260 KB Output is correct
17 Correct 20 ms 13628 KB Output is correct
18 Correct 18 ms 13524 KB Output is correct
19 Correct 19 ms 13920 KB Output is correct
20 Correct 25 ms 13908 KB Output is correct
21 Correct 20 ms 13848 KB Output is correct
22 Correct 31 ms 16064 KB Output is correct
23 Correct 11 ms 12860 KB Output is correct
24 Correct 16 ms 13652 KB Output is correct
25 Correct 7 ms 11988 KB Output is correct
26 Correct 9 ms 12372 KB Output is correct
27 Correct 364 ms 495920 KB Output is correct
28 Correct 86 ms 54220 KB Output is correct
29 Correct 447 ms 499752 KB Output is correct
30 Correct 461 ms 542804 KB Output is correct
31 Correct 456 ms 542940 KB Output is correct
32 Correct 100 ms 41932 KB Output is correct
33 Correct 434 ms 577524 KB Output is correct
34 Correct 470 ms 576656 KB Output is correct
35 Correct 359 ms 503000 KB Output is correct
36 Correct 419 ms 510476 KB Output is correct

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1095 ms 147624 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1095 ms 169060 KB Time limit exceeded
2 Halted 0 ms 0 KB -