oj.uz

Submission #638156

# Submission time Handle Problem Language Result Execution time Memory
638156 2022-09-04T19:37:59 Z blue Catfish Farm (IOI22_fish) C++17
37 / 100
 1000 ms 36652 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);
	inc[0] = dec[0] = vll{0};

	// cerr << "done\n";

	for(int r = 1; r <= N; r++)
	{
		inc[r] = dec[r] = vll(sz(fish[r]), 0);
		for(int i = 0; i < sz(fish[r]); i++)
		{
			ll basic = 0;

			if(r >= 2)
			{
				selfmax(basic, max(inc[r-2][0], dec[r-2][0]) + htwt(r-1, fish[r][i].first - 1));







				for(int j = 0; j < sz(fish[r-2]) && fish[r-2][j].first <= fish[r][i].first; 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);
				}

				for(int j = sz(fish[r-2])-1; j >= 0 && fish[r-2][j].first > fish[r][i].first; 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);
				}
			}
			selfmax(inc[r][i], basic);
			selfmax(dec[r][i], basic);
			for(int j = 0; j < sz(fish[r-1]); j++)
			{
				// cerr << "j = " << j << " , " << fish[r-1][j].first-1 << '\n';
				ll ext = 0;
				if(fish[r-1][j].first - 1 <= fish[r][i].first - 1)
				{
					// 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);
				}
				else
				{
					// 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 1082 ms 21308 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 23788 KB Output is correct
2 Correct 43 ms 23684 KB Output is correct
3 Correct 64 ms 23112 KB Output is correct
4 Correct 57 ms 24616 KB Output is correct
5 Correct 79 ms 26056 KB Output is correct
6 Correct 91 ms 26068 KB Output is correct
7 Correct 89 ms 26052 KB Output is correct
8 Correct 79 ms 26068 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 4 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 5 ms 5204 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 4 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 4 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 5 ms 5204 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 4 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 4948 KB Output is correct
16 Correct 18 ms 5152 KB Output is correct
17 Execution timed out 1094 ms 7424 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 4 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 5 ms 5204 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 4 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 4948 KB Output is correct
16 Correct 18 ms 5152 KB Output is correct
17 Execution timed out 1094 ms 7424 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 23788 KB Output is correct
2 Correct 43 ms 23684 KB Output is correct
3 Correct 64 ms 23112 KB Output is correct
4 Correct 57 ms 24616 KB Output is correct
5 Correct 79 ms 26056 KB Output is correct
6 Correct 91 ms 26068 KB Output is correct
7 Correct 89 ms 26052 KB Output is correct
8 Correct 79 ms 26068 KB Output is correct
9 Correct 95 ms 29204 KB Output is correct
10 Correct 79 ms 18896 KB Output is correct
11 Correct 139 ms 32904 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 4 ms 4948 KB Output is correct
17 Correct 2 ms 4948 KB Output is correct
18 Correct 45 ms 23728 KB Output is correct
19 Correct 46 ms 23648 KB Output is correct
20 Correct 45 ms 23672 KB Output is correct
21 Correct 60 ms 23756 KB Output is correct
22 Correct 102 ms 29724 KB Output is correct
23 Correct 154 ms 36172 KB Output is correct
24 Correct 151 ms 36652 KB Output is correct

Subtask #8
0 / 16.0

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