oj.uz

Submission #632595

# Submission time Handle Problem Language Result Execution time Memory
632595 2022-08-20T11:46:51 Z Red_Inside Catfish Farm (IOI22_fish) C++17
44 / 100
 1000 ms 66068 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=1e5+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 1033 ms 63828 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 2644 KB Output is correct
2 Execution timed out 1085 ms 66068 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 2824 KB Output is correct
2 Correct 95 ms 2808 KB Output is correct
3 Correct 421 ms 5792 KB Output is correct
4 Correct 359 ms 4888 KB Output is correct
5 Correct 688 ms 8332 KB Output is correct
6 Correct 648 ms 8404 KB Output is correct
7 Correct 675 ms 8328 KB Output is correct
8 Correct 704 ms 8320 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 3 ms 2644 KB Output is correct
10 Correct 6 ms 2772 KB Output is correct
11 Correct 5 ms 2772 KB Output is correct
12 Correct 6 ms 2772 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 4 ms 2772 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 3 ms 2644 KB Output is correct
10 Correct 6 ms 2772 KB Output is correct
11 Correct 5 ms 2772 KB Output is correct
12 Correct 6 ms 2772 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 4 ms 2772 KB Output is correct
15 Correct 4 ms 2900 KB Output is correct
16 Correct 6 ms 2772 KB Output is correct
17 Correct 109 ms 4452 KB Output is correct
18 Correct 89 ms 4812 KB Output is correct
19 Correct 120 ms 4564 KB Output is correct
20 Correct 87 ms 4688 KB Output is correct
21 Correct 79 ms 4564 KB Output is correct
22 Correct 155 ms 6436 KB Output is correct
23 Correct 85 ms 3244 KB Output is correct
24 Correct 130 ms 3924 KB Output is correct
25 Correct 8 ms 2772 KB Output is correct
26 Correct 54 ms 3156 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 3 ms 2644 KB Output is correct
10 Correct 6 ms 2772 KB Output is correct
11 Correct 5 ms 2772 KB Output is correct
12 Correct 6 ms 2772 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 4 ms 2772 KB Output is correct
15 Correct 4 ms 2900 KB Output is correct
16 Correct 6 ms 2772 KB Output is correct
17 Correct 109 ms 4452 KB Output is correct
18 Correct 89 ms 4812 KB Output is correct
19 Correct 120 ms 4564 KB Output is correct
20 Correct 87 ms 4688 KB Output is correct
21 Correct 79 ms 4564 KB Output is correct
22 Correct 155 ms 6436 KB Output is correct
23 Correct 85 ms 3244 KB Output is correct
24 Correct 130 ms 3924 KB Output is correct
25 Correct 8 ms 2772 KB Output is correct
26 Correct 54 ms 3156 KB Output is correct
27 Correct 36 ms 4544 KB Output is correct
28 Correct 504 ms 11472 KB Output is correct
29 Execution timed out 1077 ms 15276 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 2824 KB Output is correct
2 Correct 95 ms 2808 KB Output is correct
3 Correct 421 ms 5792 KB Output is correct
4 Correct 359 ms 4888 KB Output is correct
5 Correct 688 ms 8332 KB Output is correct
6 Correct 648 ms 8404 KB Output is correct
7 Correct 675 ms 8328 KB Output is correct
8 Correct 704 ms 8320 KB Output is correct
9 Execution timed out 1087 ms 44640 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 1033 ms 63828 KB Time limit exceeded
2 Halted 0 ms 0 KB -