oj.uz

답안 #638197

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
638197 2022-09-04T21:07:07 Z blue 메기 농장 (IOI22_fish) C++17
78 / 100
 1000 ms 71884 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)
{
	if(N == 2)
	{
		vvll sm(2, vll(2, 0));
		for(int j = 0; j < M; j++)
			sm[X[j]][Y[j]] += W[j];
		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];
	vll 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] = 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 <= xmx; 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]));
 
			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 = htwt(r-1, fish[r][i].first - 1);
			// cerr << prevpwt << " " << qwt << '\n';
			// assert(prevpwt == qwt);
			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;
 
				//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);
 
		}
 
		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));
		}
	}
 
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 30040 KB Output is correct
2 Correct 70 ms 33964 KB Output is correct
3 Correct 12 ms 22228 KB Output is correct
4 Correct 12 ms 22152 KB Output is correct
5 Correct 202 ms 70304 KB Output is correct
6 Correct 313 ms 71884 KB Output is correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5716 KB Output is correct
2 Execution timed out 1101 ms 34720 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 22228 KB Output is correct
2 Correct 71 ms 42524 KB Output is correct
3 Correct 85 ms 40300 KB Output is correct
4 Correct 81 ms 41668 KB Output is correct
5 Correct 129 ms 45632 KB Output is correct
6 Correct 108 ms 45672 KB Output is correct
7 Correct 114 ms 45596 KB Output is correct
8 Correct 112 ms 45632 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 4 ms 5716 KB Output is correct
4 Correct 3 ms 5716 KB Output is correct
5 Correct 3 ms 5728 KB Output is correct
6 Correct 3 ms 5716 KB Output is correct
7 Correct 3 ms 5716 KB Output is correct
8 Correct 4 ms 5716 KB Output is correct
9 Correct 3 ms 5844 KB Output is correct
10 Correct 4 ms 6100 KB Output is correct
11 Correct 4 ms 5844 KB Output is correct
12 Correct 4 ms 5980 KB Output is correct
13 Correct 3 ms 5732 KB Output is correct
14 Correct 4 ms 5972 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 4 ms 5716 KB Output is correct
4 Correct 3 ms 5716 KB Output is correct
5 Correct 3 ms 5728 KB Output is correct
6 Correct 3 ms 5716 KB Output is correct
7 Correct 3 ms 5716 KB Output is correct
8 Correct 4 ms 5716 KB Output is correct
9 Correct 3 ms 5844 KB Output is correct
10 Correct 4 ms 6100 KB Output is correct
11 Correct 4 ms 5844 KB Output is correct
12 Correct 4 ms 5980 KB Output is correct
13 Correct 3 ms 5732 KB Output is correct
14 Correct 4 ms 5972 KB Output is correct
15 Correct 4 ms 5844 KB Output is correct
16 Correct 4 ms 5972 KB Output is correct
17 Correct 22 ms 10060 KB Output is correct
18 Correct 22 ms 10708 KB Output is correct
19 Correct 21 ms 10576 KB Output is correct
20 Correct 21 ms 10540 KB Output is correct
21 Correct 24 ms 10580 KB Output is correct
22 Correct 41 ms 15292 KB Output is correct
23 Correct 7 ms 6740 KB Output is correct
24 Correct 20 ms 8708 KB Output is correct
25 Correct 5 ms 5900 KB Output is correct
26 Correct 8 ms 6624 KB Output is correct

Subtask #6
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 4 ms 5716 KB Output is correct
4 Correct 3 ms 5716 KB Output is correct
5 Correct 3 ms 5728 KB Output is correct
6 Correct 3 ms 5716 KB Output is correct
7 Correct 3 ms 5716 KB Output is correct
8 Correct 4 ms 5716 KB Output is correct
9 Correct 3 ms 5844 KB Output is correct
10 Correct 4 ms 6100 KB Output is correct
11 Correct 4 ms 5844 KB Output is correct
12 Correct 4 ms 5980 KB Output is correct
13 Correct 3 ms 5732 KB Output is correct
14 Correct 4 ms 5972 KB Output is correct
15 Correct 4 ms 5844 KB Output is correct
16 Correct 4 ms 5972 KB Output is correct
17 Correct 22 ms 10060 KB Output is correct
18 Correct 22 ms 10708 KB Output is correct
19 Correct 21 ms 10576 KB Output is correct
20 Correct 21 ms 10540 KB Output is correct
21 Correct 24 ms 10580 KB Output is correct
22 Correct 41 ms 15292 KB Output is correct
23 Correct 7 ms 6740 KB Output is correct
24 Correct 20 ms 8708 KB Output is correct
25 Correct 5 ms 5900 KB Output is correct
26 Correct 8 ms 6624 KB Output is correct
27 Correct 7 ms 7124 KB Output is correct
28 Correct 114 ms 28240 KB Output is correct
29 Correct 268 ms 34976 KB Output is correct
30 Correct 147 ms 34892 KB Output is correct
31 Correct 143 ms 34892 KB Output is correct
32 Correct 146 ms 37284 KB Output is correct
33 Correct 145 ms 34904 KB Output is correct
34 Correct 152 ms 34916 KB Output is correct
35 Correct 54 ms 17892 KB Output is correct
36 Correct 156 ms 35788 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 22228 KB Output is correct
2 Correct 71 ms 42524 KB Output is correct
3 Correct 85 ms 40300 KB Output is correct
4 Correct 81 ms 41668 KB Output is correct
5 Correct 129 ms 45632 KB Output is correct
6 Correct 108 ms 45672 KB Output is correct
7 Correct 114 ms 45596 KB Output is correct
8 Correct 112 ms 45632 KB Output is correct
9 Correct 129 ms 51120 KB Output is correct
10 Correct 84 ms 29400 KB Output is correct
11 Correct 169 ms 53260 KB Output is correct
12 Correct 4 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 5 ms 5736 KB Output is correct
18 Correct 12 ms 22220 KB Output is correct
19 Correct 14 ms 22100 KB Output is correct
20 Correct 67 ms 42484 KB Output is correct
21 Correct 67 ms 42480 KB Output is correct
22 Correct 165 ms 51612 KB Output is correct
23 Correct 172 ms 59424 KB Output is correct
24 Correct 164 ms 60736 KB Output is correct

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 30040 KB Output is correct
2 Correct 70 ms 33964 KB Output is correct
3 Correct 12 ms 22228 KB Output is correct
4 Correct 12 ms 22152 KB Output is correct
5 Correct 202 ms 70304 KB Output is correct
6 Correct 313 ms 71884 KB Output is correct
7 Correct 4 ms 5716 KB Output is correct
8 Execution timed out 1101 ms 34720 KB Time limit exceeded
9 Halted 0 ms 0 KB -