oj.uz

Submission #638177

# Submission time Handle Problem Language Result Execution time Memory
638177 2022-09-04T20:33:53 Z blue Catfish Farm (IOI22_fish) C++17
78 / 100
 1000 ms 60352 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 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);
 
 
 
 
 
				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);
 
		}
 
		int j = sz(fish[r-1]);
		ll bestval = -1'000'000'000'000'000'000LL;
 
 
		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--;
 				bestval = max(bestval, dec[r-1][j] + tot[r] - invhtwt(r, fish[r-1][j].first));
 			}
 
 			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 115 ms 39484 KB Output is correct
2 Correct 120 ms 44116 KB Output is correct
3 Correct 78 ms 35520 KB Output is correct
4 Correct 78 ms 35564 KB Output is correct
5 Correct 222 ms 59684 KB Output is correct
6 Correct 285 ms 60352 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 1087 ms 32680 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 35436 KB Output is correct
2 Correct 98 ms 35432 KB Output is correct
3 Correct 91 ms 33772 KB Output is correct
4 Correct 88 ms 36336 KB Output is correct
5 Correct 126 ms 37804 KB Output is correct
6 Correct 108 ms 37832 KB Output is correct
7 Correct 116 ms 37784 KB Output is correct
8 Correct 113 ms 37764 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 4 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 4 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 3 ms 5792 KB Output is correct
12 Correct 3 ms 5844 KB Output is correct
13 Correct 3 ms 5716 KB Output is correct
14 Correct 3 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 4 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 4 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 3 ms 5792 KB Output is correct
12 Correct 3 ms 5844 KB Output is correct
13 Correct 3 ms 5716 KB Output is correct
14 Correct 3 ms 5844 KB Output is correct
15 Correct 3 ms 5844 KB Output is correct
16 Correct 4 ms 5972 KB Output is correct
17 Correct 52 ms 9516 KB Output is correct
18 Correct 30 ms 10028 KB Output is correct
19 Correct 27 ms 9940 KB Output is correct
20 Correct 26 ms 9884 KB Output is correct
21 Correct 27 ms 9908 KB Output is correct
22 Correct 55 ms 14012 KB Output is correct
23 Correct 7 ms 6612 KB Output is correct
24 Correct 18 ms 8360 KB Output is correct
25 Correct 4 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 4 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 4 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 3 ms 5792 KB Output is correct
12 Correct 3 ms 5844 KB Output is correct
13 Correct 3 ms 5716 KB Output is correct
14 Correct 3 ms 5844 KB Output is correct
15 Correct 3 ms 5844 KB Output is correct
16 Correct 4 ms 5972 KB Output is correct
17 Correct 52 ms 9516 KB Output is correct
18 Correct 30 ms 10028 KB Output is correct
19 Correct 27 ms 9940 KB Output is correct
20 Correct 26 ms 9884 KB Output is correct
21 Correct 27 ms 9908 KB Output is correct
22 Correct 55 ms 14012 KB Output is correct
23 Correct 7 ms 6612 KB Output is correct
24 Correct 18 ms 8360 KB Output is correct
25 Correct 4 ms 5844 KB Output is correct
26 Correct 7 ms 6484 KB Output is correct
27 Correct 8 ms 6768 KB Output is correct
28 Correct 162 ms 24836 KB Output is correct
29 Correct 344 ms 31796 KB Output is correct
30 Correct 162 ms 31440 KB Output is correct
31 Correct 170 ms 31568 KB Output is correct
32 Correct 197 ms 32672 KB Output is correct
33 Correct 165 ms 31544 KB Output is correct
34 Correct 166 ms 31436 KB Output is correct
35 Correct 62 ms 16592 KB Output is correct
36 Correct 183 ms 32992 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 35436 KB Output is correct
2 Correct 98 ms 35432 KB Output is correct
3 Correct 91 ms 33772 KB Output is correct
4 Correct 88 ms 36336 KB Output is correct
5 Correct 126 ms 37804 KB Output is correct
6 Correct 108 ms 37832 KB Output is correct
7 Correct 116 ms 37784 KB Output is correct
8 Correct 113 ms 37764 KB Output is correct
9 Correct 161 ms 40892 KB Output is correct
10 Correct 83 ms 25092 KB Output is correct
11 Correct 189 ms 44608 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 5720 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 81 ms 35516 KB Output is correct
19 Correct 75 ms 35500 KB Output is correct
20 Correct 79 ms 35436 KB Output is correct
21 Correct 77 ms 35460 KB Output is correct
22 Correct 196 ms 42480 KB Output is correct
23 Correct 197 ms 50884 KB Output is correct
24 Correct 202 ms 51388 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 39484 KB Output is correct
2 Correct 120 ms 44116 KB Output is correct
3 Correct 78 ms 35520 KB Output is correct
4 Correct 78 ms 35564 KB Output is correct
5 Correct 222 ms 59684 KB Output is correct
6 Correct 285 ms 60352 KB Output is correct
7 Correct 3 ms 5716 KB Output is correct
8 Execution timed out 1087 ms 32680 KB Time limit exceeded
9 Halted 0 ms 0 KB -