oj.uz

Submission #652458

# Submission time Handle Problem Language Result Execution time Memory
652458 2022-10-22T17:05:59 Z blue Catfish Farm (IOI22_fish) C++17
78 / 100
 1000 ms 65680 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())
 
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);
 
ll max_weights(int N, int M, vi X, vi Y, vi W)
{
	vvll sm(2, vll(N, 0));
	for(int j = 0; j < M; j++)
		if(X[j] < 2)
			sm[X[j]][Y[j]] += W[j];
 
	if(N == 2)
	{
		return max(sm[0][0] + sm[0][1], sm[1][0] + sm[1][1]);
	}

 
	int xmx = 0;
	for(int j = 0; j < M; j++)
	{
		X[j]++;
		xmx = max(xmx, X[j] + 2);
		Y[j]++;
	}
	xmx = min(xmx, N);
 
	// cerr << "xmx = " << xmx << '\n';
 
	vpll fish[1+N];
	ll* fishpref[1+N];
 
	vpii fishbyY[1+N];
 
	for(int j = 0; j < M; j++)
	{
		// fish[X[j]].push_back({Y[j], W[j]});
		fishbyY[Y[j]].push_back({X[j], W[j]});
		tot[X[j]] += W[j];
	}
 
	for(int y = 0; y <= N; y++)
		for(pii z : fishbyY[y])
			fish[z.first].push_back({y, z.second});
 
	for(int r = 1; r <= xmx; 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] = new ll[sz(fish[r])];
		for(int i = 0; i < sz(fish[r]); i++)
		{
			fishpref[r][i] = (i == 0 ? 0 : fishpref[r][i-1]) + fish[r][i].second;
		}
	}
 
	fish[0] = vpll{{0, 0}};
	fishpref[0] = new ll[1];
	fishpref[0][0] = 0;
 
	// vvll inc(1+N), dec(1+N);
	ll* inc[1+N];
	ll* dec[1+N];
	ll* incpref[1+N];
	ll* decpref[1+N]; //pref inc dec mx
	inc[0] = new ll[1];
	inc[0][0] = 0;

	dec[0] = new ll[1];
	dec[0][0] = 0;
 
 	ll res = 0;
	// cerr << "done\n";
 
	for(int r = 1; r <= xmx; r++)
	{
		incpref[r-1] = new ll[sz(fish[r-1])];
		decpref[r-1] = new ll[sz(fish[r-1])];

		incpref[r-1][0] = decpref[r-1][0] = 0;

		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);
		inc[r] = new ll[sz(fish[r])];
		dec[r] = new ll[sz(fish[r])];
		for(int i = 0; i < sz(fish[r]); i++)
			inc[r][i] = dec[r][i] = 0;
 
 
 
 
 
 
		vll Csuff;
		if(r >= 2)
		{
			Csuff = vll(sz(fish[r-2]));
 
			int pi = sz(fish[r-1])-1;
			ll pwt = tot[r-1];
 
			for(int j = sz(fish[r-2])-1; j >= 0; j--)
			{
				while(pi >= 0 && fish[r-1][pi].first > fish[r-2][j].first - 1)
				{
					pwt -= fish[r-1][pi].second;
					pi--;
				}
 
				// Csuff[j] = max(inc[r-2][j], dec[r-2][j]) + htwt(r-1, fish[r-2][j].first - 1);
				Csuff[j] = max(inc[r-2][j], dec[r-2][j]) + pwt;
				if(j+1 < sz(fish[r-2]))
					selfmax(Csuff[j], Csuff[j+1]);
			}
		}
 
 
		ll Dmx = 0;
		ll Did = -1;
 
		int ppi = -1;
 		int qi = -1;
 		ll qwt = 0;
 
		for(int i = 0; i < sz(fish[r]); i++)
		{
			ll basic = 0;
 
			ll Bcatch = 0;
			int Bk = -1;
 
			while(qi+1 < sz(fish[r-1]) && fish[r-1][qi+1].first <= fish[r][i].first - 1)
			{
				qi++;
				qwt += fish[r-1][qi].second;
			}
			ll prevpwt = qwt;
 
			ll constD = -(tot[r-1] - prevpwt) + tot[r-1];
 
			if(r >= 2)
			{
				//A
				selfmax(basic, max(inc[r-2][0], dec[r-2][0]) + prevpwt);
 
 
 
 
 				while(ppi+1 < sz(fish[r-2]) && fish[r-2][ppi+1].first <= fish[r][i].first)
 					ppi++;
				int ploci = ppi;
 
				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;
				}
				assert(Bk == qi);
				selfmax(basic, Bcatch + max(incpref[r-2][ploci], decpref[r-2][ploci]));
	
				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));
			}
 
			selfmax(inc[r][i], Dmx + constD);
			selfmax(dec[r][i], Dmx + constD);
 
		}
 
		int j = sz(fish[r-1]);
		ll bestval = -1'000'000'000'000'000'000LL;
 
		int ri = sz(fish[r]);
		ll rwt = 0;
 
 
		for(int i = sz(fish[r])-1; i >= 0; i--)
		{
 			while(j-1 >= 0 && fish[r-1][j-1].first > fish[r][i].first)
 			{
 				j--;
 				while(ri-1 >= 0 && fish[r][ri-1].first >= fish[r-1][j].first)
 				{
 					ri--;
 					rwt += fish[r][ri].second;
 				}
 				bestval = max(bestval, dec[r-1][j] + tot[r] - rwt);
 			}
 
 			selfmax(dec[r][i], bestval - (i >= 1 ? fishpref[r][i-1] : 0));
		}

		for(int i = 0; i < sz(fish[r]); i++)
			selfmax(res, max(inc[r][i], dec[r][i]));
	}
 
	return res;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 24328 KB Output is correct
2 Correct 83 ms 27744 KB Output is correct
3 Correct 10 ms 15952 KB Output is correct
4 Correct 9 ms 15940 KB Output is correct
5 Correct 207 ms 64056 KB Output is correct
6 Correct 281 ms 65680 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5716 KB Output is correct
2 Execution timed out 1083 ms 29048 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15940 KB Output is correct
2 Correct 56 ms 36220 KB Output is correct
3 Correct 75 ms 34740 KB Output is correct
4 Correct 56 ms 35416 KB Output is correct
5 Correct 89 ms 39328 KB Output is correct
6 Correct 95 ms 39356 KB Output is correct
7 Correct 85 ms 39332 KB Output is correct
8 Correct 93 ms 39352 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 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 5680 KB Output is correct
9 Correct 3 ms 5844 KB Output is correct
10 Correct 4 ms 6092 KB Output is correct
11 Correct 3 ms 5844 KB Output is correct
12 Correct 4 ms 5964 KB Output is correct
13 Correct 4 ms 5716 KB Output is correct
14 Correct 4 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 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 5680 KB Output is correct
9 Correct 3 ms 5844 KB Output is correct
10 Correct 4 ms 6092 KB Output is correct
11 Correct 3 ms 5844 KB Output is correct
12 Correct 4 ms 5964 KB Output is correct
13 Correct 4 ms 5716 KB Output is correct
14 Correct 4 ms 5844 KB Output is correct
15 Correct 3 ms 5844 KB Output is correct
16 Correct 4 ms 5972 KB Output is correct
17 Correct 24 ms 10068 KB Output is correct
18 Correct 24 ms 10700 KB Output is correct
19 Correct 23 ms 10540 KB Output is correct
20 Correct 24 ms 10532 KB Output is correct
21 Correct 23 ms 10460 KB Output is correct
22 Correct 47 ms 15192 KB Output is correct
23 Correct 8 ms 6740 KB Output is correct
24 Correct 18 ms 8660 KB Output is correct
25 Correct 4 ms 5972 KB Output is correct
26 Correct 7 ms 6612 KB Output is correct

Subtask #6
17.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 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 5680 KB Output is correct
9 Correct 3 ms 5844 KB Output is correct
10 Correct 4 ms 6092 KB Output is correct
11 Correct 3 ms 5844 KB Output is correct
12 Correct 4 ms 5964 KB Output is correct
13 Correct 4 ms 5716 KB Output is correct
14 Correct 4 ms 5844 KB Output is correct
15 Correct 3 ms 5844 KB Output is correct
16 Correct 4 ms 5972 KB Output is correct
17 Correct 24 ms 10068 KB Output is correct
18 Correct 24 ms 10700 KB Output is correct
19 Correct 23 ms 10540 KB Output is correct
20 Correct 24 ms 10532 KB Output is correct
21 Correct 23 ms 10460 KB Output is correct
22 Correct 47 ms 15192 KB Output is correct
23 Correct 8 ms 6740 KB Output is correct
24 Correct 18 ms 8660 KB Output is correct
25 Correct 4 ms 5972 KB Output is correct
26 Correct 7 ms 6612 KB Output is correct
27 Correct 6 ms 6868 KB Output is correct
28 Correct 137 ms 28288 KB Output is correct
29 Correct 347 ms 34904 KB Output is correct
30 Correct 148 ms 34640 KB Output is correct
31 Correct 155 ms 34656 KB Output is correct
32 Correct 179 ms 37460 KB Output is correct
33 Correct 153 ms 34652 KB Output is correct
34 Correct 156 ms 34640 KB Output is correct
35 Correct 61 ms 17652 KB Output is correct
36 Correct 160 ms 35664 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15940 KB Output is correct
2 Correct 56 ms 36220 KB Output is correct
3 Correct 75 ms 34740 KB Output is correct
4 Correct 56 ms 35416 KB Output is correct
5 Correct 89 ms 39328 KB Output is correct
6 Correct 95 ms 39356 KB Output is correct
7 Correct 85 ms 39332 KB Output is correct
8 Correct 93 ms 39352 KB Output is correct
9 Correct 98 ms 44824 KB Output is correct
10 Correct 65 ms 26328 KB Output is correct
11 Correct 194 ms 46784 KB Output is correct
12 Correct 3 ms 5716 KB Output is correct
13 Correct 3 ms 5716 KB Output is correct
14 Correct 3 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 3 ms 5716 KB Output is correct
18 Correct 9 ms 15960 KB Output is correct
19 Correct 10 ms 15940 KB Output is correct
20 Correct 46 ms 36280 KB Output is correct
21 Correct 47 ms 36244 KB Output is correct
22 Correct 126 ms 45348 KB Output is correct
23 Correct 146 ms 53196 KB Output is correct
24 Correct 144 ms 54576 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 24328 KB Output is correct
2 Correct 83 ms 27744 KB Output is correct
3 Correct 10 ms 15952 KB Output is correct
4 Correct 9 ms 15940 KB Output is correct
5 Correct 207 ms 64056 KB Output is correct
6 Correct 281 ms 65680 KB Output is correct
7 Correct 5 ms 5716 KB Output is correct
8 Execution timed out 1083 ms 29048 KB Time limit exceeded
9 Halted 0 ms 0 KB -