oj.uz

Submission #638172

# Submission time Handle Problem Language Result Execution time Memory
638172 2022-09-04T20:23:35 Z blue Catfish Farm (IOI22_fish) C++17
12 / 100
 1000 ms 60256 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);

		}

		//type E transition

		int ej = sz(fish[r-1]);
		ll bestval = 0;

		for(int i = sz(fish[r])-1; i >= 0; i--)
		{
 			while(ej-1 >= 0 && fish[r-1][ej-1].first > fish[r][i].first)
 			{
 				ej--;
 				bestval = max(bestval, dec[r-1][ej] + tot[r] - (i >= 1 ? fishpref[r][i-1] : 0) - invhtwt(r, fish[r-1][ej].first));
 			}
 			selfmax(dec[r][i], bestval);
			// 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 110 ms 39488 KB Output is correct
2 Correct 126 ms 44184 KB Output is correct
3 Correct 86 ms 35480 KB Output is correct
4 Correct 83 ms 35404 KB Output is correct
5 Correct 230 ms 59624 KB Output is correct
6 Correct 297 ms 60256 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 1089 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 87 ms 35440 KB Output is correct
2 Correct 84 ms 35512 KB Output is correct
3 Correct 99 ms 33764 KB Output is correct
4 Correct 94 ms 36300 KB Output is correct
5 Correct 119 ms 37868 KB Output is correct
6 Correct 119 ms 37944 KB Output is correct
7 Correct 119 ms 37832 KB Output is correct
8 Correct 122 ms 37792 KB Output is correct

Subtask #4
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 4 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 4 ms 5716 KB Output is correct
8 Correct 3 ms 5716 KB Output is correct
9 Incorrect 3 ms 5844 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '216366270048'
10 Halted 0 ms 0 KB -

Subtask #5
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 4 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 4 ms 5716 KB Output is correct
8 Correct 3 ms 5716 KB Output is correct
9 Incorrect 3 ms 5844 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '216366270048'
10 Halted 0 ms 0 KB -

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 4 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 4 ms 5716 KB Output is correct
8 Correct 3 ms 5716 KB Output is correct
9 Incorrect 3 ms 5844 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '216366270048'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 35440 KB Output is correct
2 Correct 84 ms 35512 KB Output is correct
3 Correct 99 ms 33764 KB Output is correct
4 Correct 94 ms 36300 KB Output is correct
5 Correct 119 ms 37868 KB Output is correct
6 Correct 119 ms 37944 KB Output is correct
7 Correct 119 ms 37832 KB Output is correct
8 Correct 122 ms 37792 KB Output is correct
9 Correct 141 ms 40976 KB Output is correct
10 Correct 87 ms 25140 KB Output is correct
11 Incorrect 183 ms 44664 KB 1st lines differ - on the 1st token, expected: '72889508713304', found: '72889208890328'
12 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 39488 KB Output is correct
2 Correct 126 ms 44184 KB Output is correct
3 Correct 86 ms 35480 KB Output is correct
4 Correct 83 ms 35404 KB Output is correct
5 Correct 230 ms 59624 KB Output is correct
6 Correct 297 ms 60256 KB Output is correct
7 Correct 3 ms 5716 KB Output is correct
8 Execution timed out 1089 ms 32696 KB Time limit exceeded
9 Halted 0 ms 0 KB -