oj.uz

Submission #632512

# Submission time Handle Problem Language Result Execution time Memory
632512 2022-08-20T08:43:42 Z Red_Inside Catfish Farm (IOI22_fish) C++17
35 / 100
 1000 ms 171200 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];

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;
	}
	forn(2, i, n)
	{
		dp1[i] = 0;
		forn(1, j, n)
		{
			dp[i][j][0] = dp2[i-1]+pref[i-1][j];
			forn(1, k, j-1)
			{
				dp[i][j][0] = max(dp[i - 1][k][0] + pref[i-1][j] - pref[i-1][k],
				dp[i][j][0]);
			}
			forn(1, k, n)
			{
				dp[i][j][0]=max(max(dp[i-2][k][0],dp[i-2][k][1])+pref[i-1][max(j, k)],
				dp[i][j][0]);
			}
			dp[i][j][1] = -inf;
			forn(j + 1, k, n)
			{
				dp[i][j][1] = max(dp[i][j][1], max(dp[i-1][k][0], dp[i-1][k][1])
				+pref[i][k]-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]);
	}
	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 1089 ms 171200 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Execution timed out 1090 ms 169692 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 1103 ms 157384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 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 12 ms 2644 KB Output is correct
10 Correct 86 ms 6180 KB Output is correct
11 Correct 12 ms 2696 KB Output is correct
12 Correct 93 ms 6040 KB Output is correct
13 Correct 2 ms 1364 KB Output is correct
14 Correct 85 ms 6036 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 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 12 ms 2644 KB Output is correct
10 Correct 86 ms 6180 KB Output is correct
11 Correct 12 ms 2696 KB Output is correct
12 Correct 93 ms 6040 KB Output is correct
13 Correct 2 ms 1364 KB Output is correct
14 Correct 85 ms 6036 KB Output is correct
15 Correct 87 ms 6012 KB Output is correct
16 Correct 3 ms 1236 KB Output is correct
17 Correct 91 ms 7756 KB Output is correct
18 Correct 96 ms 7608 KB Output is correct
19 Correct 95 ms 8148 KB Output is correct
20 Correct 119 ms 8160 KB Output is correct
21 Correct 106 ms 8068 KB Output is correct
22 Correct 105 ms 10188 KB Output is correct
23 Correct 83 ms 6928 KB Output is correct
24 Correct 89 ms 7864 KB Output is correct
25 Correct 96 ms 6140 KB Output is correct
26 Correct 91 ms 6600 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 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 12 ms 2644 KB Output is correct
10 Correct 86 ms 6180 KB Output is correct
11 Correct 12 ms 2696 KB Output is correct
12 Correct 93 ms 6040 KB Output is correct
13 Correct 2 ms 1364 KB Output is correct
14 Correct 85 ms 6036 KB Output is correct
15 Correct 87 ms 6012 KB Output is correct
16 Correct 3 ms 1236 KB Output is correct
17 Correct 91 ms 7756 KB Output is correct
18 Correct 96 ms 7608 KB Output is correct
19 Correct 95 ms 8148 KB Output is correct
20 Correct 119 ms 8160 KB Output is correct
21 Correct 106 ms 8068 KB Output is correct
22 Correct 105 ms 10188 KB Output is correct
23 Correct 83 ms 6928 KB Output is correct
24 Correct 89 ms 7864 KB Output is correct
25 Correct 96 ms 6140 KB Output is correct
26 Correct 91 ms 6600 KB Output is correct
27 Execution timed out 1095 ms 97252 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1103 ms 157384 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 1089 ms 171200 KB Time limit exceeded
2 Halted 0 ms 0 KB -