oj.uz

Submission #638174

# Submission time Handle Problem Language Result Execution time Memory
638174 2022-09-04T20:27:34 Z blue Catfish Farm (IOI22_fish) C++17
61 / 100
 1000 ms 60240 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vvpii = vector<vpii>;
using vi = vector<int>;
using vvi = vector<vi>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
#define sz(x) int(x.size())
 
const int lg = 18;
 
void selfmax(ll& a, ll b)
{
	a = max(a, b);
}
 
const int maxN = 100'000;
 
vpll fish[1 + maxN];
vll fishpref[1 + maxN];
vll tot(1 + maxN, 0);
 
int maxind(int i, int h)
{
	//return max ind of col i so that corresponding height is <= h
	int b = -1;
	for(int e = lg; e >= 0; e--)
	{
		if(b + (1<<e) < sz(fish[i]) && fish[i][b + (1<<e)].first <= h)
			b += (1<<e);
	}
	return b;
}
 
ll htwt(int i, int h)
{
	int j = maxind(i, h);
	if(j == -1)
		return 0;
	else
		return fishpref[i][j];
}
 
ll invhtwt(int i, int h)
{
	return tot[i] - htwt(i, h-1);
}
 
ll max_weights(int N, int M, vi X, vi Y, vi W)
{
	for(int j = 0; j < M; j++)
	{
		X[j]++;
		Y[j]++;
	}
 
	// vpll fish[1+N];
	// vll fishpref[1+N];
 
	for(int j = 0; j < M; j++)
	{
		fish[X[j]].push_back({Y[j], W[j]});
		tot[X[j]] += W[j];
	}
 
	for(int r = 1; r <= N; r++)
	{
		fish[r].push_back({N+1, 0});
		sort(fish[r].begin(), fish[r].end());
 
		if(fish[r][0].first != 1)
		{
			fish[r].insert(fish[r].begin(), {1, 0});
		}
 
		fishpref[r] = vll(sz(fish[r]));
		for(int i = 0; i < sz(fishpref[r]); i++)
		{
			fishpref[r][i] = (i == 0 ? 0 : fishpref[r][i-1]) + fish[r][i].second;
		}
	}
 
	fish[0] = vpll{{0, 0}};
	fishpref[0] = vll{0};
 
	vvll inc(1+N), dec(1+N);
	vvll incpref(1+N), decpref(1+N); //pref inc dec mx
	inc[0] = dec[0] = vll{0};
 
	// cerr << "done\n";
 
	for(int r = 1; r <= N; r++)
	{
		incpref[r-1] = inc[r-1];
		decpref[r-1] = dec[r-1];
		for(int i = 1; i < sz(fish[r-1]); i++)
		{
			incpref[r-1][i] = max(incpref[r-1][i-1], inc[r-1][i]);
			decpref[r-1][i] = max(decpref[r-1][i-1], dec[r-1][i]);
		}
 
 
		inc[r] = dec[r] = vll(sz(fish[r]), 0);
 
 
 
 
 
 
		vll Csuff;
		if(r >= 2)
		{
			Csuff = vll(sz(fish[r-2]));
			for(int j = sz(fish[r-2])-1; j >= 0; j--)
			{
				Csuff[j] = max(inc[r-2][j], dec[r-2][j]) + htwt(r-1, fish[r-2][j].first - 1);
				if(j+1 < sz(fish[r-2]))
					selfmax(Csuff[j], Csuff[j+1]);
			}
		}
 
 
		ll Dmx = 0;
		ll Did = -1;
 
 
		for(int i = 0; i < sz(fish[r]); i++)
		{
			ll basic = 0;
 
			ll Bcatch = 0;
			int Bk = -1;
 
			ll constD = -invhtwt(r-1, fish[r][i].first) + tot[r-1];
 
			if(r >= 2)
			{
				//A
				selfmax(basic, max(inc[r-2][0], dec[r-2][0]) + htwt(r-1, fish[r][i].first - 1));
 
 
 
 
 
				int ploci = maxind(r-2, fish[r][i].first);
 
				//B
				/*for(int j = 0; j <= ploci; j++)
				{
					// cerr << "j = " << j << " out of (exc) " << sz(fish[r-2]) << '\n';
					ll medcatch = 0;
					for(int k = 0; k < sz(fish[r-1]); k++)
						if(fish[r-1][k].first <= fish[r][i].first - 1)
							medcatch += fish[r-1][k].second;
 
					selfmax(basic, max(inc[r-2][j], dec[r-2][j]) + medcatch);
				}*/
				while(Bk+1 < sz(fish[r-1]) && fish[r-1][Bk+1].first <= fish[r][i].first - 1)
				{
					Bk++;
					Bcatch += fish[r-1][Bk].second;
				}
				selfmax(basic, Bcatch + max(incpref[r-2][ploci], decpref[r-2][ploci]));
				// for(int j = 0; j <= ploci; j++)
				// {
				// 	// cerr << "j = " << j << " out of (exc) " << sz(fish[r-2]) << '\n';
					
 
				// 	// selfmax(basic, max(inc[r-2][j], dec[r-2][j]) + Bcatch);
				// 	selfmax(basic, )
				// }
 
 
				//C
				// for(int j = sz(fish[r-2])-1; j > ploci; j--)
				// {
				// 	// cerr << "j = " << j << " out of (exc) " << sz(fish[r-2]) << '\n';
				// 	ll medcatch = 0;
				// 	for(int k = 0; k < sz(fish[r-1]); k++)
				// 		if(fish[r-1][k].first <= fish[r-2][j].first - 1)
				// 			medcatch += fish[r-1][k].second;
 
				// 	selfmax(basic, max(inc[r-2][j], dec[r-2][j]) + medcatch);
				// }
 
				if(ploci+1 < sz(fish[r-2]))
				{
					// cerr << ploci << " : " << sz(fish[r-2]) << '\n';
					selfmax(basic, Csuff[ploci+1]);
				}
			}
 
			selfmax(inc[r][i], basic);
			selfmax(dec[r][i], basic);
 
			//type D transition
 
			while(Did+1 < sz(fish[r-1]) && fish[r-1][Did+1].first <= fish[r][i].first)
			{
				Did++;
				Dmx = max(Dmx, inc[r-1][Did] - (Did >= 1 ? fishpref[r-1][Did-1] : 0));
			}
 
			// for(int j = 0; j < sz(fish[r-1]) && fish[r-1][j].first <= fish[r][i].first; j++)
			// {
			// 	// cerr << "j = " << j << " , " << fish[r-1][j].first-1 << '\n';
			// 	// ll ext = 0;
				
			// 	// cerr << "case 1\n";
			// 	// for(int k = j; k < sz(fish[r-1]); k++)
			// 	// {
			// 	// 	if(fish[r-1][k].first <= fish[r][i].first - 1)
			// 	// 		ext += fish[r-1][k].second;
			// 	// }
			// 	// if(j >= 1)
			// 	// 	ext -= fishpref[r-1][j-1];
			// 	// ll ext = -invhtwt(r-1, fish[r][i].first);
 
			// 	selfmax(inc[r][i], inc[r-1][j] - (j >= 1 ? fishpref[r-1][j-1] : 0) + constD);
			// 	selfmax(dec[r][i], inc[r-1][j] - (j >= 1 ? fishpref[r-1][j-1] : 0) + constD);
			// }
			selfmax(inc[r][i], Dmx + constD);
			selfmax(dec[r][i], Dmx + constD);
 
		}
 
		for(int i = sz(fish[r])-1; i >= 0; i--)
		{
 
			for(int j = sz(fish[r-1])-1; j >= 0 && fish[r-1][j].first > fish[r][i].first; j--)
			{
				
				// ll ext = 0;
				// // cerr << "case 2\n";
				// for(int k = i; k < sz(fish[r]); k++)
				// {
				// 	if(fish[r][k].first <= fish[r-1][j].first - 1)
				// 		ext += fish[r][k].second;
				// }
 
				// ll ext = tot[r];
				// if(i >= 1)
				// 	ext -= fishpref[r][i-1];
				// ext -= invhtwt(r, fish[r-1][j].first);
 
				selfmax(dec[r][i], dec[r-1][j] + tot[r] - (i >= 1 ? fishpref[r][i-1] : 0) - invhtwt(r, fish[r-1][j].first));
				// cerr << r << ' ' << fish[r][i].first-1 << " : " << inc[r][i] << ' ' << dec[r][i] << '\n';		
		
			}
		}
	}
 
	ll res = 0;
	for(vll x : inc)
		for(ll y : x)
			res = max(res, y);
	for(vll x : dec)
		for(ll y : x)
			res = max(res, y);
 
	return res;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 39512 KB Output is correct
2 Correct 134 ms 44072 KB Output is correct
3 Correct 89 ms 35476 KB Output is correct
4 Correct 92 ms 35492 KB Output is correct
5 Correct 261 ms 59780 KB Output is correct
6 Correct 308 ms 60240 KB Output is correct

Subtask #2
0 / 6.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 35404 KB Output is correct
2 Correct 87 ms 35512 KB Output is correct
3 Correct 102 ms 33720 KB Output is correct
4 Correct 103 ms 36304 KB Output is correct
5 Correct 132 ms 37940 KB Output is correct
6 Correct 124 ms 37980 KB Output is correct
7 Correct 129 ms 37752 KB Output is correct
8 Correct 124 ms 37812 KB Output is correct

Subtask #4
14.0 / 14.0

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

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 3 ms 5716 KB Output is correct
4 Correct 3 ms 5716 KB Output is correct
5 Correct 3 ms 5716 KB Output is correct
6 Correct 3 ms 5768 KB Output is correct
7 Correct 3 ms 5716 KB Output is correct
8 Correct 3 ms 5716 KB Output is correct
9 Correct 4 ms 5844 KB Output is correct
10 Correct 4 ms 5972 KB Output is correct
11 Correct 4 ms 5844 KB Output is correct
12 Correct 4 ms 5844 KB Output is correct
13 Correct 3 ms 5716 KB Output is correct
14 Correct 4 ms 5844 KB Output is correct
15 Correct 5 ms 5844 KB Output is correct
16 Correct 5 ms 5972 KB Output is correct
17 Correct 152 ms 9452 KB Output is correct
18 Correct 187 ms 9988 KB Output is correct
19 Correct 113 ms 9940 KB Output is correct
20 Correct 107 ms 9936 KB Output is correct
21 Correct 103 ms 9864 KB Output is correct
22 Correct 393 ms 14112 KB Output is correct
23 Correct 10 ms 6656 KB Output is correct
24 Correct 55 ms 8304 KB Output is correct
25 Correct 4 ms 5972 KB Output is correct
26 Correct 10 ms 6484 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 3 ms 5716 KB Output is correct
4 Correct 3 ms 5716 KB Output is correct
5 Correct 3 ms 5716 KB Output is correct
6 Correct 3 ms 5768 KB Output is correct
7 Correct 3 ms 5716 KB Output is correct
8 Correct 3 ms 5716 KB Output is correct
9 Correct 4 ms 5844 KB Output is correct
10 Correct 4 ms 5972 KB Output is correct
11 Correct 4 ms 5844 KB Output is correct
12 Correct 4 ms 5844 KB Output is correct
13 Correct 3 ms 5716 KB Output is correct
14 Correct 4 ms 5844 KB Output is correct
15 Correct 5 ms 5844 KB Output is correct
16 Correct 5 ms 5972 KB Output is correct
17 Correct 152 ms 9452 KB Output is correct
18 Correct 187 ms 9988 KB Output is correct
19 Correct 113 ms 9940 KB Output is correct
20 Correct 107 ms 9936 KB Output is correct
21 Correct 103 ms 9864 KB Output is correct
22 Correct 393 ms 14112 KB Output is correct
23 Correct 10 ms 6656 KB Output is correct
24 Correct 55 ms 8304 KB Output is correct
25 Correct 4 ms 5972 KB Output is correct
26 Correct 10 ms 6484 KB Output is correct
27 Correct 7 ms 6740 KB Output is correct
28 Execution timed out 1090 ms 21920 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 35404 KB Output is correct
2 Correct 87 ms 35512 KB Output is correct
3 Correct 102 ms 33720 KB Output is correct
4 Correct 103 ms 36304 KB Output is correct
5 Correct 132 ms 37940 KB Output is correct
6 Correct 124 ms 37980 KB Output is correct
7 Correct 129 ms 37752 KB Output is correct
8 Correct 124 ms 37812 KB Output is correct
9 Correct 143 ms 41024 KB Output is correct
10 Correct 91 ms 25136 KB Output is correct
11 Correct 190 ms 44752 KB Output is correct
12 Correct 3 ms 5716 KB Output is correct
13 Correct 3 ms 5716 KB Output is correct
14 Correct 3 ms 5716 KB Output is correct
15 Correct 3 ms 5716 KB Output is correct
16 Correct 3 ms 5716 KB Output is correct
17 Correct 3 ms 5716 KB Output is correct
18 Correct 87 ms 35448 KB Output is correct
19 Correct 88 ms 35468 KB Output is correct
20 Correct 109 ms 35404 KB Output is correct
21 Correct 95 ms 35452 KB Output is correct
22 Correct 170 ms 42448 KB Output is correct
23 Correct 223 ms 50784 KB Output is correct
24 Correct 214 ms 51516 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 39512 KB Output is correct
2 Correct 134 ms 44072 KB Output is correct
3 Correct 89 ms 35476 KB Output is correct
4 Correct 92 ms 35492 KB Output is correct
5 Correct 261 ms 59780 KB Output is correct
6 Correct 308 ms 60240 KB Output is correct
7 Correct 3 ms 5716 KB Output is correct
8 Execution timed out 1088 ms 32684 KB Time limit exceeded
9 Halted 0 ms 0 KB -