oj.uz

Submission #638162

# Submission time Handle Problem Language Result Execution time Memory
638162 2022-09-04T20:01:21 Z blue Catfish Farm (IOI22_fish) C++17
37 / 100
 1000 ms 50728 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];

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 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]});
	}

	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);

			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;
				}

				selfmax(inc[r][i], inc[r-1][j] + ext);
				selfmax(dec[r][i], inc[r-1][j] + 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;
				}

				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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 26812 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 34636 KB Output is correct
2 Correct 72 ms 34624 KB Output is correct
3 Correct 87 ms 33024 KB Output is correct
4 Correct 84 ms 35532 KB Output is correct
5 Correct 109 ms 37032 KB Output is correct
6 Correct 110 ms 37060 KB Output is correct
7 Correct 118 ms 37044 KB Output is correct
8 Correct 110 ms 36972 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4992 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 4 ms 5204 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 5076 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4992 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 4 ms 5204 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 5076 KB Output is correct
15 Correct 3 ms 5076 KB Output is correct
16 Correct 9 ms 5204 KB Output is correct
17 Execution timed out 1092 ms 8540 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4992 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 4 ms 5204 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 5076 KB Output is correct
15 Correct 3 ms 5076 KB Output is correct
16 Correct 9 ms 5204 KB Output is correct
17 Execution timed out 1092 ms 8540 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 34636 KB Output is correct
2 Correct 72 ms 34624 KB Output is correct
3 Correct 87 ms 33024 KB Output is correct
4 Correct 84 ms 35532 KB Output is correct
5 Correct 109 ms 37032 KB Output is correct
6 Correct 110 ms 37060 KB Output is correct
7 Correct 118 ms 37044 KB Output is correct
8 Correct 110 ms 36972 KB Output is correct
9 Correct 127 ms 40160 KB Output is correct
10 Correct 85 ms 24304 KB Output is correct
11 Correct 165 ms 43876 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 2 ms 4996 KB Output is correct
14 Correct 2 ms 4948 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 2 ms 4948 KB Output is correct
18 Correct 75 ms 34636 KB Output is correct
19 Correct 70 ms 34636 KB Output is correct
20 Correct 73 ms 34636 KB Output is correct
21 Correct 71 ms 34644 KB Output is correct
22 Correct 157 ms 41760 KB Output is correct
23 Correct 188 ms 49996 KB Output is correct
24 Correct 181 ms 50728 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 26812 KB Time limit exceeded
2 Halted 0 ms 0 KB -