oj.uz

Submission #638168

# Submission time Handle Problem Language Result Execution time Memory
638168 2022-09-04T20:14:17 Z blue Catfish Farm (IOI22_fish) C++17
61 / 100
 1000 ms 60320 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]);
			}
		}
 
		for(int i = 0; i < sz(fish[r]); i++)
		{
			ll basic = 0;
 
			ll Bcatch = 0;
			int Bk = -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
 
			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], tot[r-1] + inc[r-1][j] - (j >= 1 ? fishpref[r-1][j-1] : 0) + ext);
				selfmax(dec[r][i], tot[r-1] + inc[r-1][j] - (j >= 1 ? fishpref[r-1][j-1] : 0) + ext);
			}
 
			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 117 ms 39436 KB Output is correct
2 Correct 135 ms 44084 KB Output is correct
3 Correct 106 ms 35476 KB Output is correct
4 Correct 88 ms 35404 KB Output is correct
5 Correct 254 ms 59664 KB Output is correct
6 Correct 311 ms 60320 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 1094 ms 32696 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 35428 KB Output is correct
2 Correct 110 ms 35480 KB Output is correct
3 Correct 109 ms 33724 KB Output is correct
4 Correct 102 ms 36312 KB Output is correct
5 Correct 129 ms 37768 KB Output is correct
6 Correct 126 ms 37796 KB Output is correct
7 Correct 128 ms 37756 KB Output is correct
8 Correct 137 ms 37840 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 4 ms 5744 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 5 ms 5972 KB Output is correct
11 Correct 4 ms 5844 KB Output is correct
12 Correct 4 ms 5972 KB Output is correct
13 Correct 3 ms 5716 KB Output is correct
14 Correct 5 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 4 ms 5744 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 5 ms 5972 KB Output is correct
11 Correct 4 ms 5844 KB Output is correct
12 Correct 4 ms 5972 KB Output is correct
13 Correct 3 ms 5716 KB Output is correct
14 Correct 5 ms 5844 KB Output is correct
15 Correct 3 ms 5844 KB Output is correct
16 Correct 7 ms 5972 KB Output is correct
17 Correct 323 ms 9468 KB Output is correct
18 Correct 341 ms 9944 KB Output is correct
19 Correct 184 ms 9932 KB Output is correct
20 Correct 246 ms 9900 KB Output is correct
21 Correct 186 ms 9936 KB Output is correct
22 Correct 768 ms 13992 KB Output is correct
23 Correct 14 ms 6612 KB Output is correct
24 Correct 110 ms 8348 KB Output is correct
25 Correct 4 ms 5844 KB Output is correct
26 Correct 12 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 4 ms 5744 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 5 ms 5972 KB Output is correct
11 Correct 4 ms 5844 KB Output is correct
12 Correct 4 ms 5972 KB Output is correct
13 Correct 3 ms 5716 KB Output is correct
14 Correct 5 ms 5844 KB Output is correct
15 Correct 3 ms 5844 KB Output is correct
16 Correct 7 ms 5972 KB Output is correct
17 Correct 323 ms 9468 KB Output is correct
18 Correct 341 ms 9944 KB Output is correct
19 Correct 184 ms 9932 KB Output is correct
20 Correct 246 ms 9900 KB Output is correct
21 Correct 186 ms 9936 KB Output is correct
22 Correct 768 ms 13992 KB Output is correct
23 Correct 14 ms 6612 KB Output is correct
24 Correct 110 ms 8348 KB Output is correct
25 Correct 4 ms 5844 KB Output is correct
26 Correct 12 ms 6484 KB Output is correct
27 Correct 7 ms 6740 KB Output is correct
28 Execution timed out 1082 ms 20048 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 35428 KB Output is correct
2 Correct 110 ms 35480 KB Output is correct
3 Correct 109 ms 33724 KB Output is correct
4 Correct 102 ms 36312 KB Output is correct
5 Correct 129 ms 37768 KB Output is correct
6 Correct 126 ms 37796 KB Output is correct
7 Correct 128 ms 37756 KB Output is correct
8 Correct 137 ms 37840 KB Output is correct
9 Correct 197 ms 40940 KB Output is correct
10 Correct 93 ms 25160 KB Output is correct
11 Correct 197 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 4 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 4 ms 5716 KB Output is correct
18 Correct 96 ms 35408 KB Output is correct
19 Correct 88 ms 35464 KB Output is correct
20 Correct 86 ms 35472 KB Output is correct
21 Correct 90 ms 35404 KB Output is correct
22 Correct 176 ms 42624 KB Output is correct
23 Correct 236 ms 50880 KB Output is correct
24 Correct 236 ms 51388 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 39436 KB Output is correct
2 Correct 135 ms 44084 KB Output is correct
3 Correct 106 ms 35476 KB Output is correct
4 Correct 88 ms 35404 KB Output is correct
5 Correct 254 ms 59664 KB Output is correct
6 Correct 311 ms 60320 KB Output is correct
7 Correct 3 ms 5716 KB Output is correct
8 Execution timed out 1094 ms 32696 KB Time limit exceeded
9 Halted 0 ms 0 KB -