oj.uz

Submission #638180

# Submission time Handle Problem Language Result Execution time Memory
638180 2022-09-04T20:40:41 Z blue Catfish Farm (IOI22_fish) C++17
78 / 100
 1000 ms 60236 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]));

			int pi = sz(fish[r-1])-1;
			ll pwt = tot[r-1];

			for(int j = sz(fish[r-2])-1; j >= 0; j--)
			{
				while(pi >= 0 && fish[r-1][pi].first > fish[r-2][j].first - 1)
				{
					pwt -= fish[r-1][pi].second;
					pi--;
				}

				// Csuff[j] = max(inc[r-2][j], dec[r-2][j]) + htwt(r-1, fish[r-2][j].first - 1);
				Csuff[j] = max(inc[r-2][j], dec[r-2][j]) + pwt;
				if(j+1 < sz(fish[r-2]))
					selfmax(Csuff[j], Csuff[j+1]);
			}
		}
 
 
		ll Dmx = 0;
		ll Did = -1;

		int ppi = -1;
 
 
		for(int i = 0; i < sz(fish[r]); i++)
		{
			ll basic = 0;
 
			ll Bcatch = 0;
			int Bk = -1;

			ll prevpwt = htwt(r-1, fish[r][i].first - 1);
 
			ll constD = -(tot[r-1] - prevpwt) + tot[r-1];
 
			if(r >= 2)
			{
				//A
				selfmax(basic, max(inc[r-2][0], dec[r-2][0]) + prevpwt);
 
 
 
 
 				while(ppi+1 < sz(fish[r-2]) && fish[r-2][ppi+1].first <= fish[r][i].first)
 					ppi++;
				int ploci = ppi;
 
				//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);
 
		}
 
		int j = sz(fish[r-1]);
		ll bestval = -1'000'000'000'000'000'000LL;

		int ri = sz(fish[r]);
		ll rwt = 0;
 
 
		for(int i = sz(fish[r])-1; i >= 0; i--)
		{
 			while(j-1 >= 0 && fish[r-1][j-1].first > fish[r][i].first)
 			{
 				j--;
 				while(ri-1 >= 0 && fish[r][ri-1].first >= fish[r-1][j].first)
 				{
 					ri--;
 					rwt += fish[r][ri].second;
 				}
 				bestval = max(bestval, dec[r-1][j] + tot[r] - rwt);
 			}
 
 			selfmax(dec[r][i], bestval - (i >= 1 ? fishpref[r][i-1] : 0));
		}
	}
 
	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 93 ms 39484 KB Output is correct
2 Correct 113 ms 44116 KB Output is correct
3 Correct 82 ms 35404 KB Output is correct
4 Correct 68 ms 35448 KB Output is correct
5 Correct 195 ms 59692 KB Output is correct
6 Correct 273 ms 60236 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5716 KB Output is correct
2 Execution timed out 1089 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 66 ms 35412 KB Output is correct
2 Correct 67 ms 35444 KB Output is correct
3 Correct 88 ms 33800 KB Output is correct
4 Correct 102 ms 36308 KB Output is correct
5 Correct 106 ms 37840 KB Output is correct
6 Correct 100 ms 37756 KB Output is correct
7 Correct 124 ms 37864 KB Output is correct
8 Correct 114 ms 37808 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 5716 KB Output is correct
7 Correct 3 ms 5716 KB Output is correct
8 Correct 3 ms 5716 KB Output is correct
9 Correct 3 ms 5844 KB Output is correct
10 Correct 4 ms 5972 KB Output is correct
11 Correct 3 ms 5856 KB Output is correct
12 Correct 3 ms 5844 KB Output is correct
13 Correct 3 ms 5708 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 5716 KB Output is correct
7 Correct 3 ms 5716 KB Output is correct
8 Correct 3 ms 5716 KB Output is correct
9 Correct 3 ms 5844 KB Output is correct
10 Correct 4 ms 5972 KB Output is correct
11 Correct 3 ms 5856 KB Output is correct
12 Correct 3 ms 5844 KB Output is correct
13 Correct 3 ms 5708 KB Output is correct
14 Correct 4 ms 5844 KB Output is correct
15 Correct 4 ms 5844 KB Output is correct
16 Correct 5 ms 5972 KB Output is correct
17 Correct 28 ms 9488 KB Output is correct
18 Correct 27 ms 9940 KB Output is correct
19 Correct 23 ms 9912 KB Output is correct
20 Correct 24 ms 9940 KB Output is correct
21 Correct 23 ms 9892 KB Output is correct
22 Correct 48 ms 13992 KB Output is correct
23 Correct 7 ms 6532 KB Output is correct
24 Correct 17 ms 8392 KB Output is correct
25 Correct 5 ms 5844 KB Output is correct
26 Correct 7 ms 6484 KB Output is correct

Subtask #6
17.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 5716 KB Output is correct
7 Correct 3 ms 5716 KB Output is correct
8 Correct 3 ms 5716 KB Output is correct
9 Correct 3 ms 5844 KB Output is correct
10 Correct 4 ms 5972 KB Output is correct
11 Correct 3 ms 5856 KB Output is correct
12 Correct 3 ms 5844 KB Output is correct
13 Correct 3 ms 5708 KB Output is correct
14 Correct 4 ms 5844 KB Output is correct
15 Correct 4 ms 5844 KB Output is correct
16 Correct 5 ms 5972 KB Output is correct
17 Correct 28 ms 9488 KB Output is correct
18 Correct 27 ms 9940 KB Output is correct
19 Correct 23 ms 9912 KB Output is correct
20 Correct 24 ms 9940 KB Output is correct
21 Correct 23 ms 9892 KB Output is correct
22 Correct 48 ms 13992 KB Output is correct
23 Correct 7 ms 6532 KB Output is correct
24 Correct 17 ms 8392 KB Output is correct
25 Correct 5 ms 5844 KB Output is correct
26 Correct 7 ms 6484 KB Output is correct
27 Correct 6 ms 6740 KB Output is correct
28 Correct 139 ms 24824 KB Output is correct
29 Correct 324 ms 31732 KB Output is correct
30 Correct 153 ms 31440 KB Output is correct
31 Correct 156 ms 31436 KB Output is correct
32 Correct 176 ms 32732 KB Output is correct
33 Correct 149 ms 31560 KB Output is correct
34 Correct 153 ms 31564 KB Output is correct
35 Correct 60 ms 16488 KB Output is correct
36 Correct 176 ms 32912 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 35412 KB Output is correct
2 Correct 67 ms 35444 KB Output is correct
3 Correct 88 ms 33800 KB Output is correct
4 Correct 102 ms 36308 KB Output is correct
5 Correct 106 ms 37840 KB Output is correct
6 Correct 100 ms 37756 KB Output is correct
7 Correct 124 ms 37864 KB Output is correct
8 Correct 114 ms 37808 KB Output is correct
9 Correct 117 ms 40952 KB Output is correct
10 Correct 76 ms 25152 KB Output is correct
11 Correct 214 ms 44604 KB Output is correct
12 Correct 3 ms 5716 KB Output is correct
13 Correct 3 ms 5680 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 70 ms 35444 KB Output is correct
19 Correct 68 ms 35500 KB Output is correct
20 Correct 73 ms 35492 KB Output is correct
21 Correct 68 ms 35448 KB Output is correct
22 Correct 138 ms 42508 KB Output is correct
23 Correct 187 ms 50888 KB Output is correct
24 Correct 193 ms 51516 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 39484 KB Output is correct
2 Correct 113 ms 44116 KB Output is correct
3 Correct 82 ms 35404 KB Output is correct
4 Correct 68 ms 35448 KB Output is correct
5 Correct 195 ms 59692 KB Output is correct
6 Correct 273 ms 60236 KB Output is correct
7 Correct 4 ms 5716 KB Output is correct
8 Execution timed out 1089 ms 32684 KB Time limit exceeded
9 Halted 0 ms 0 KB -