oj.uz

Submission #632590

# Submission time Handle Problem Language Result Execution time Memory
632590 2022-08-20T11:41:07 Z Red_Inside Catfish Farm (IOI22_fish) C++17
44 / 100
 1000 ms 68632 KB 
//
#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=2e5+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, dp[4][maxn][2], dp1[maxn], dp2[maxn], c[maxn];
ll t[4*maxn][3][4], pu[4*maxn][3][4];
vector <pii> vec[maxn];

void push(int v, int tl, int tr, int x, int ty)
{
	if(ty == 3)
	{
		if(pu[v][x][ty] == -1)
		{
			pu[v * 2][x][ty] = -1;
			pu[v * 2 + 1][x][ty] = -1;
			t[v * 2][x][ty] = 0;
			t[v * 2 + 1][x][ty] = 0;
			pu[v][x][ty] = 0;
		}
	}
	else
	{
		if(pu[v][x][ty] == -inf)
		{
			pu[v * 2][x][ty] = -inf;
			pu[v * 2 + 1][x][ty] = -inf;
			t[v * 2][x][ty] = -inf;
			t[v * 2 + 1][x][ty] = -inf;
			pu[v][x][ty] = 0;
		}
	}
}

void upd(int v, int tl, int tr, int pos, ll val, int x, int ty)
{
	if(pos < tl || tr < pos) return;
	if(tl == tr)
	{
		t[v][x][ty] = val;
		return;
	}
	push(v, tl, tr, x, ty);
	upd(v * 2, tl, (tl + tr) / 2, pos, val, x, ty);
	upd(v * 2 + 1, (tl + tr) / 2 + 1, tr, pos, val, x, ty);
	if(ty == 3) t[v][x][ty] = t[v * 2][x][ty] + t[v * 2 + 1][x][ty];
	else
		t[v][x][ty] = max(t[v * 2][x][ty], t[v * 2 + 1][x][ty]);
}

ll get(int v, int tl, int tr, int l, int r, int x, int ty)
{
	if(l > tr || r < tl) return (ty == 3 ? 0 : -inf);
	if(l <= tl && tr <= r) return t[v][x][ty];
	push(v, tl, tr, x, ty);
	ll r1 = get(v * 2, tl, (tl + tr) / 2, l, r, x, ty);
	ll r2 = get(v * 2 + 1, (tl + tr) / 2 + 1, tr, l, r, x, ty);
	if(ty == 3) return r1 + r2;
	return max(r1, r2);
}

ll max_weights(int N, int m, vector <int> x, vector <int> y, vector <int> C)
{
	n = N;
	forn(0, i, m-1)
	{
		vec[x[i]+1].pb({y[i]+1, C[i]});
	}
	set <int> pos;
	for(auto j : vec[1])
	{
		c[j.f]++;
		if(c[j.f] == 1)
			pos.insert(j.f);
		if(j.f>1)
		{
			c[j.f-1]++;
			if(c[j.f-1]==1)
				pos.insert(j.f-1);
		}
		if(j.f<n)
		{
			c[j.f+1]++;
			if(c[j.f+1]==1)
				pos.insert(j.f+1);
		}
	}
	for(auto j : vec[2])
	{
		c[j.f]++;
		if(c[j.f] == 1)
			pos.insert(j.f);
		if(j.f>1)
		{
			c[j.f-1]++;
			if(c[j.f-1]==1)
				pos.insert(j.f-1);
		}
		if(j.f<n)
		{
			c[j.f+1]++;
			if(c[j.f+1]==1)
				pos.insert(j.f+1);
		}
	}
	forn(0, i, 2)
	{
		forn(0, j, 2)
		{
			pu[1][i][j] = -inf;
			t[1][i][j] = -inf;
		}
		t[1][i][3] = 0;
		pu[1][i][3] = -1;
	}
	int p = 0;
	for(auto j : vec[1])
	{
		upd(1, 1, n, j.f, j.s, p, 3);
	}
	for(auto j : pos)
	{
		dp[p][j][0] = 0;
	}
	dp1[p] = 0;
	dp2[p] = 0;
	for(auto j : pos)
	{
		upd(1, 1, n, j, max(dp[p][j][0], dp[p][j][1]), p, 1);
		upd(1, 1, n, j, dp[p][j][0] - get(1, 1, n, 1, j, p, 3), p, 0);
	}
	c[n]++;
	if(c[n] == 1) pos.insert(n);
	forn(2, i, n)
	{
		p = (p + 1) % 3;
		t[1][p][0] = -inf;
		t[1][p][1] = -inf;
		t[1][p][2] = -inf;
		t[1][p][3] = 0;
		pu[1][p][0] = -inf;
		pu[1][p][1] = -inf;
		pu[1][p][2] = -inf;
		pu[1][p][3] = -1;
		for(auto j : vec[i])
		{
			upd(1, 1, n, j.f, j.s, p, 3);
		}
		for(auto j : vec[i + 1])
		{
			c[j.f]++;
			if(c[j.f]==1)
				pos.insert(j.f);
			if(j.f>1)
			{
				c[j.f-1]++;
				if(c[j.f-1]==1)
					pos.insert(j.f-1);
			}
			if(j.f<n)
			{
				c[j.f+1]++;
				if(c[j.f+1]==1)
					pos.insert(j.f+1);
			}
		}
		if(i - 4 >= 1)
		{
			for(auto j : vec[i - 4])
			{
				c[j.f]--;
				if(c[j.f] == 0)
					pos.erase(j.f);
				if(j.f>1)
				{
					c[j.f-1]--;
					if(c[j.f-1]==0)
						pos.erase(j.f-1);
				}
				if(j.f<n)
				{
					c[j.f+1]--;
					if(c[j.f+1]==0)
						pos.erase(j.f+1);
				}
			}
		}
		for(auto j : pos)
		{
			dp[p][j][0] = -inf;
			dp[p][j][1] = -inf;
			upd(1, 1, n, j, max(dp[(p-1+3)%3][j][0],dp[(p-1+3)%3][j][1])+get(1, 1, n, 1, j, p, 3), (p-1+3)%3, 2);
		}
		dp1[p] = 0;
		for(auto j : pos)
		{
			dp[p][j][0] = max(dp[p][j][0], 
			dp2[(p-1+3)%3]+get(1, 1, n, 1, j, (p-1+3)%3, 3));
			dp[p][j][0] = max(dp[p][j][0], 
			get(1, 1, n, 1, j-1, (p-1+3)%3, 0)+get(1, 1, n, 1, j, (p-1+3)%3, 3));
			dp[p][j][0] = max(dp[p][j][0], 
			get(1, 1, n, 1, j, (p-2+3)%3, 1)+get(1, 1, n, 1, j, (p-1+3)%3, 3));
			dp[p][j][0] = max(dp[p][j][0],
			get(1, 1, n, j+1, n,(p-2+3)%3, 2));
			dp[p][j][1] = -inf;
			dp[p][j][1] = max(dp[p][j][1], 
			get(1, 1, n, j+1, n, (p-1+3)%3, 2)-get(1, 1, n, 1, j, p, 3));
		}
		dp1[p] = max(dp1[p], get(1, 1, n, 1, n, (p-1+3)%3, 2));
		dp2[p] = max(dp2[(p-1+3)%3], dp1[(p-1+3)%3]);
		for(auto j : pos)
		{
//			cout << i << " " << j << " " << dp[p][j][0] << " " << dp[p][j][1] << endl;
			upd(1, 1, n, j, max(dp[p][j][0], dp[p][j][1]), p, 1);
			upd(1, 1, n, j, dp[p][j][0] - get(1, 1, n, 1, j, p, 3), p, 0);
		}
	}
	ll ans = 0;
	for(auto i : pos)
	{
		ans = max(ans, dp[p][i][0]);
		ans = max(ans, dp[p][i][1]);
	}
	ans = max(ans, dp1[p]);
	ans = max(ans, dp2[p]);
	return ans;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 5132 KB Output is correct
2 Correct 98 ms 5188 KB Output is correct
3 Correct 406 ms 8824 KB Output is correct
4 Correct 371 ms 7340 KB Output is correct
5 Correct 673 ms 10732 KB Output is correct
6 Correct 654 ms 11372 KB Output is correct
7 Correct 660 ms 11992 KB Output is correct
8 Correct 650 ms 11980 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 4 ms 5076 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4944 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 4 ms 5076 KB Output is correct
10 Correct 8 ms 5116 KB Output is correct
11 Correct 5 ms 5076 KB Output is correct
12 Correct 7 ms 5076 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 6 ms 5164 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 4 ms 5076 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4944 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 4 ms 5076 KB Output is correct
10 Correct 8 ms 5116 KB Output is correct
11 Correct 5 ms 5076 KB Output is correct
12 Correct 7 ms 5076 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 6 ms 5164 KB Output is correct
15 Correct 5 ms 5204 KB Output is correct
16 Correct 7 ms 5076 KB Output is correct
17 Correct 114 ms 6812 KB Output is correct
18 Correct 95 ms 7116 KB Output is correct
19 Correct 105 ms 6960 KB Output is correct
20 Correct 82 ms 6996 KB Output is correct
21 Correct 80 ms 6964 KB Output is correct
22 Correct 161 ms 8784 KB Output is correct
23 Correct 104 ms 5596 KB Output is correct
24 Correct 148 ms 6316 KB Output is correct
25 Correct 9 ms 5076 KB Output is correct
26 Correct 60 ms 5460 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 4 ms 5076 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4944 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 4 ms 5076 KB Output is correct
10 Correct 8 ms 5116 KB Output is correct
11 Correct 5 ms 5076 KB Output is correct
12 Correct 7 ms 5076 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 6 ms 5164 KB Output is correct
15 Correct 5 ms 5204 KB Output is correct
16 Correct 7 ms 5076 KB Output is correct
17 Correct 114 ms 6812 KB Output is correct
18 Correct 95 ms 7116 KB Output is correct
19 Correct 105 ms 6960 KB Output is correct
20 Correct 82 ms 6996 KB Output is correct
21 Correct 80 ms 6964 KB Output is correct
22 Correct 161 ms 8784 KB Output is correct
23 Correct 104 ms 5596 KB Output is correct
24 Correct 148 ms 6316 KB Output is correct
25 Correct 9 ms 5076 KB Output is correct
26 Correct 60 ms 5460 KB Output is correct
27 Correct 43 ms 6836 KB Output is correct
28 Correct 526 ms 15692 KB Output is correct
29 Execution timed out 1030 ms 19304 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 5132 KB Output is correct
2 Correct 98 ms 5188 KB Output is correct
3 Correct 406 ms 8824 KB Output is correct
4 Correct 371 ms 7340 KB Output is correct
5 Correct 673 ms 10732 KB Output is correct
6 Correct 654 ms 11372 KB Output is correct
7 Correct 660 ms 11992 KB Output is correct
8 Correct 650 ms 11980 KB Output is correct
9 Execution timed out 1057 ms 40956 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

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