oj.uz

Submission #632596

# Submission time Handle Problem Language Result Execution time Memory
632596 2022-08-20T11:47:59 Z Red_Inside Catfish Farm (IOI22_fish) C++17
44 / 100
 1000 ms 66660 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 Correct 941 ms 63184 KB Output is correct
2 Execution timed out 1083 ms 66660 KB Time limit exceeded
3 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 1083 ms 66160 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 2828 KB Output is correct
2 Correct 101 ms 2812 KB Output is correct
3 Correct 286 ms 5788 KB Output is correct
4 Correct 235 ms 4772 KB Output is correct
5 Correct 413 ms 8328 KB Output is correct
6 Correct 395 ms 8324 KB Output is correct
7 Correct 440 ms 8328 KB Output is correct
8 Correct 405 ms 8336 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2672 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2596 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 3 ms 2644 KB Output is correct
10 Correct 6 ms 2856 KB Output is correct
11 Correct 4 ms 2772 KB Output is correct
12 Correct 5 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 1 ms 2644 KB Output is correct
2 Correct 2 ms 2672 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2596 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 3 ms 2644 KB Output is correct
10 Correct 6 ms 2856 KB Output is correct
11 Correct 4 ms 2772 KB Output is correct
12 Correct 5 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 5 ms 2900 KB Output is correct
16 Correct 6 ms 2772 KB Output is correct
17 Correct 115 ms 4464 KB Output is correct
18 Correct 86 ms 4692 KB Output is correct
19 Correct 127 ms 4672 KB Output is correct
20 Correct 80 ms 4616 KB Output is correct
21 Correct 83 ms 4564 KB Output is correct
22 Correct 152 ms 6420 KB Output is correct
23 Correct 56 ms 3232 KB Output is correct
24 Correct 116 ms 3964 KB Output is correct
25 Correct 6 ms 2772 KB Output is correct
26 Correct 43 ms 3088 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2672 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2596 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 3 ms 2644 KB Output is correct
10 Correct 6 ms 2856 KB Output is correct
11 Correct 4 ms 2772 KB Output is correct
12 Correct 5 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 5 ms 2900 KB Output is correct
16 Correct 6 ms 2772 KB Output is correct
17 Correct 115 ms 4464 KB Output is correct
18 Correct 86 ms 4692 KB Output is correct
19 Correct 127 ms 4672 KB Output is correct
20 Correct 80 ms 4616 KB Output is correct
21 Correct 83 ms 4564 KB Output is correct
22 Correct 152 ms 6420 KB Output is correct
23 Correct 56 ms 3232 KB Output is correct
24 Correct 116 ms 3964 KB Output is correct
25 Correct 6 ms 2772 KB Output is correct
26 Correct 43 ms 3088 KB Output is correct
27 Correct 33 ms 4540 KB Output is correct
28 Correct 540 ms 11472 KB Output is correct
29 Execution timed out 1093 ms 15180 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 2828 KB Output is correct
2 Correct 101 ms 2812 KB Output is correct
3 Correct 286 ms 5788 KB Output is correct
4 Correct 235 ms 4772 KB Output is correct
5 Correct 413 ms 8328 KB Output is correct
6 Correct 395 ms 8324 KB Output is correct
7 Correct 440 ms 8328 KB Output is correct
8 Correct 405 ms 8336 KB Output is correct
9 Execution timed out 1092 ms 49004 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 941 ms 63184 KB Output is correct
2 Execution timed out 1083 ms 66660 KB Time limit exceeded
3 Halted 0 ms 0 KB -