oj.uz

Submission #638157

# Submission time Handle Problem Language Result Execution time Memory
638157 2022-09-04T19:38:58 Z blue Catfish Farm (IOI22_fish) C++17
37 / 100
 1000 ms 36664 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));





				int ploci = maxind(r-2, fish[r][i].first);

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

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

			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 1093 ms 21232 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 26400 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 23776 KB Output is correct
2 Correct 50 ms 23768 KB Output is correct
3 Correct 61 ms 23152 KB Output is correct
4 Correct 63 ms 24596 KB Output is correct
5 Correct 85 ms 26108 KB Output is correct
6 Correct 92 ms 26016 KB Output is correct
7 Correct 111 ms 26140 KB Output is correct
8 Correct 82 ms 26048 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 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 4 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 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 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 4 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 16 ms 5152 KB Output is correct
17 Execution timed out 1091 ms 7404 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 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 4 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 16 ms 5152 KB Output is correct
17 Execution timed out 1091 ms 7404 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 23776 KB Output is correct
2 Correct 50 ms 23768 KB Output is correct
3 Correct 61 ms 23152 KB Output is correct
4 Correct 63 ms 24596 KB Output is correct
5 Correct 85 ms 26108 KB Output is correct
6 Correct 92 ms 26016 KB Output is correct
7 Correct 111 ms 26140 KB Output is correct
8 Correct 82 ms 26048 KB Output is correct
9 Correct 109 ms 29204 KB Output is correct
10 Correct 69 ms 18892 KB Output is correct
11 Correct 141 ms 32816 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct
14 Correct 2 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 4 ms 4948 KB Output is correct
18 Correct 48 ms 23752 KB Output is correct
19 Correct 50 ms 23676 KB Output is correct
20 Correct 46 ms 23684 KB Output is correct
21 Correct 47 ms 23756 KB Output is correct
22 Correct 111 ms 29652 KB Output is correct
23 Correct 161 ms 36152 KB Output is correct
24 Correct 166 ms 36664 KB Output is correct

Subtask #8
0 / 16.0

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