oj.uz

Submission #638170

# Submission time Handle Problem Language Result Execution time Memory
638170 2022-09-04T20:17:25 Z blue Catfish Farm (IOI22_fish) C++17
61 / 100
 1000 ms 60244 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 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] + ext);
				// 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 115 ms 39404 KB Output is correct
2 Correct 133 ms 44068 KB Output is correct
3 Correct 86 ms 35480 KB Output is correct
4 Correct 88 ms 35404 KB Output is correct
5 Correct 239 ms 59700 KB Output is correct
6 Correct 303 ms 60244 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 1083 ms 32676 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 35396 KB Output is correct
2 Correct 88 ms 35404 KB Output is correct
3 Correct 100 ms 33812 KB Output is correct
4 Correct 101 ms 36480 KB Output is correct
5 Correct 131 ms 37800 KB Output is correct
6 Correct 120 ms 37836 KB Output is correct
7 Correct 122 ms 37872 KB Output is correct
8 Correct 124 ms 37836 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 5 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 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 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 5 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 3 ms 5844 KB Output is correct
15 Correct 3 ms 5844 KB Output is correct
16 Correct 5 ms 5972 KB Output is correct
17 Correct 151 ms 9484 KB Output is correct
18 Correct 178 ms 10072 KB Output is correct
19 Correct 100 ms 9928 KB Output is correct
20 Correct 107 ms 9928 KB Output is correct
21 Correct 103 ms 9892 KB Output is correct
22 Correct 388 ms 13940 KB Output is correct
23 Correct 10 ms 6612 KB Output is correct
24 Correct 56 ms 8260 KB Output is correct
25 Correct 6 ms 5844 KB Output is correct
26 Correct 11 ms 6476 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 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 5 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 3 ms 5844 KB Output is correct
15 Correct 3 ms 5844 KB Output is correct
16 Correct 5 ms 5972 KB Output is correct
17 Correct 151 ms 9484 KB Output is correct
18 Correct 178 ms 10072 KB Output is correct
19 Correct 100 ms 9928 KB Output is correct
20 Correct 107 ms 9928 KB Output is correct
21 Correct 103 ms 9892 KB Output is correct
22 Correct 388 ms 13940 KB Output is correct
23 Correct 10 ms 6612 KB Output is correct
24 Correct 56 ms 8260 KB Output is correct
25 Correct 6 ms 5844 KB Output is correct
26 Correct 11 ms 6476 KB Output is correct
27 Correct 7 ms 6740 KB Output is correct
28 Execution timed out 1100 ms 21880 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 35396 KB Output is correct
2 Correct 88 ms 35404 KB Output is correct
3 Correct 100 ms 33812 KB Output is correct
4 Correct 101 ms 36480 KB Output is correct
5 Correct 131 ms 37800 KB Output is correct
6 Correct 120 ms 37836 KB Output is correct
7 Correct 122 ms 37872 KB Output is correct
8 Correct 124 ms 37836 KB Output is correct
9 Correct 146 ms 40964 KB Output is correct
10 Correct 89 ms 25164 KB Output is correct
11 Correct 184 ms 44620 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 2 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 90 ms 35448 KB Output is correct
19 Correct 86 ms 35436 KB Output is correct
20 Correct 87 ms 35428 KB Output is correct
21 Correct 91 ms 35492 KB Output is correct
22 Correct 169 ms 42548 KB Output is correct
23 Correct 214 ms 51024 KB Output is correct
24 Correct 216 ms 51396 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 39404 KB Output is correct
2 Correct 133 ms 44068 KB Output is correct
3 Correct 86 ms 35480 KB Output is correct
4 Correct 88 ms 35404 KB Output is correct
5 Correct 239 ms 59700 KB Output is correct
6 Correct 303 ms 60244 KB Output is correct
7 Correct 3 ms 5716 KB Output is correct
8 Execution timed out 1083 ms 32676 KB Time limit exceeded
9 Halted 0 ms 0 KB -