oj.uz

답안 #626296

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
626296 2022-08-11T11:06:07 Z TheLostCookie 메기 농장 (IOI22_fish) C++17
75 / 100
 1000 ms 75760 KB 
#include <bits/stdc++.h>
#include "fish.h"
using namespace std;

typedef long long int lli;
typedef vector<lli> vi;
typedef pair<int,int> ii;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ROF(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define pb push_back
#define fi first
#define se second
#define all(v) begin(v),end(v)

const int INF = 2e9;

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
	map<ii,lli> inc, dec;
	inc[{-1,-INF}] = inc[{-1,INF}] = 0;
	
	vector<pair<ii,lli>> ptw;
	ptw.reserve(M+N);
	FOR(i,0,M) ptw.pb({{X[i],Y[i]},W[i]});
	FOR(i,0,N) ptw.pb({{i,INF},0});
	sort(all(ptw));
	
	vector<ii> pts;
	FOR(i,0,M+N) {
		pts.pb(ptw[i].fi);
	}
	
	//const op
	vector<vector<int>> cols(N);
	vector<vi> wts(N);
	FOR(i,0,M+N) {
		int c = ptw[i].fi.fi,r=ptw[i].fi.se;
		cols[c].pb(r);
		if(wts[c].empty()) wts[c].pb(0);
		wts[c].pb(wts[c].back()+ptw[i].se);
	}	
	
	//counts fish in [{x,y1},{x,y2}], inclusive of endpoints
	function<lli(lli,lli,lli)> countFish = [&] (lli x, lli y1, lli y2) {
		if(x < 0 || x >= N || y1 > y2) return 0LL;
		else {
			int l = lower_bound(all(cols[x]),y1) - begin(cols[x]);
			int r = upper_bound(all(cols[x]),y2) - begin(cols[x]);
			return wts[x][r]-wts[x][l];
		}
	};
	
	map<ii,lli> colInc[3];
	map<ii,lli> colDec;
	FOR(i,0,N) {	
		int l = lower_bound(all(pts), ii{i,0}) - begin(pts);
		int r = lower_bound(all(pts), ii{i+1,0}) - begin(pts);
		
		int p = lower_bound(all(pts), ii{i-2,0}) - begin(pts);
		FOR(j,l,r) {
			if(j>l) colInc[0][pts[j]]=max(colInc[0][pts[j]],colInc[0][pts[j-1]]);
			while(p<int(pts.size())&&pts[p].fi==i-2&&pts[p].se<=pts[j].se) {
				colInc[0][pts[j]]=max(colInc[0][pts[j]],dec[pts[p]]);
				p++;
			}
		}
		
		FOR(j,l,r) colInc[0][pts[j]] += countFish(i-1,0,pts[j].se-1);
		p = lower_bound(all(pts), ii{i-2,0}) - begin(pts);
		while(p<int(pts.size())&&pts[p].fi==i-2) colInc[1][pts[l]] = max(colInc[1][pts[l]],dec[pts[p]]+countFish(i-1,0,pts[p].se-1)),p++;
		FOR(j,l+1,r) colInc[1][pts[j]] = max(colInc[1][pts[j]],colInc[1][pts[j-1]]);
		
		p = lower_bound(all(pts), ii{i-1,0}) - begin(pts);
		FOR(j,l,r) {
			if(j>l) colInc[2][pts[j]]=max(colInc[2][pts[j]],colInc[2][pts[j-1]]+countFish(i-1,pts[j-1].se,pts[j].se-1));
			while(p<int(pts.size())&&pts[p].fi==i-1&&pts[p].se<=pts[j].se) {
				colInc[2][pts[j]]=max(colInc[2][pts[j]],inc[pts[p]]+countFish(i-1,pts[p].se,pts[j].se-1));
				p++;
			}
		}
		
		p = lower_bound(all(pts), ii{i-1,INF}) - begin(pts);
		ROF(j,l,r) {
			if(i>0&&j<r-1) colDec[pts[j]]=max(colDec[pts[j]],colDec[pts[j+1]]+countFish(i,pts[j].se,pts[j+1].se-1));
			while(p>=0&&pts[p].fi==i-1&&pts[p].se>=pts[j].se) {
				colDec[pts[j]]=max(colDec[pts[j]],dec[pts[p]]+countFish(i,pts[j].se,pts[p].se-1));
				p--;
			}
		}
		
		FOR(j,l,r) {
			FOR(k,0,3) {
				inc[pts[j]] = max(inc[pts[j]],colInc[k][pts[j]]);
			}
			dec[pts[j]] = max(dec[pts[j]],colDec[pts[j]]);
		}
		dec[ii{i,INF}] = max(inc[ii{i,INF}],dec[ii{i,INF}]);
		
		while(!inc.empty() && inc.begin()->fi.fi < i-1) inc.erase(inc.begin());
		while(!dec.empty() && dec.begin()->fi.fi < i-1) dec.erase(dec.begin());
		FOR(j,0,3) colInc[j].clear();
		colDec.clear();
	}
	
	lli ans = max(inc[{N-1,INF}],dec.lower_bound({N-1,0})->second);
	
	return ans;
}

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 416 ms 47656 KB Output is correct
2 Correct 527 ms 57308 KB Output is correct
3 Correct 86 ms 13604 KB Output is correct
4 Correct 83 ms 13500 KB Output is correct
5 Execution timed out 1087 ms 65496 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 882 ms 62792 KB Output is correct
3 Execution timed out 1095 ms 75760 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 13604 KB Output is correct
2 Correct 115 ms 13600 KB Output is correct
3 Correct 138 ms 15644 KB Output is correct
4 Correct 134 ms 16012 KB Output is correct
5 Correct 201 ms 20028 KB Output is correct
6 Correct 192 ms 20240 KB Output is correct
7 Correct 218 ms 20264 KB Output is correct
8 Correct 203 ms 20224 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 4 ms 468 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 3 ms 488 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 2 ms 340 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 4 ms 468 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 3 ms 488 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 5 ms 468 KB Output is correct
17 Correct 121 ms 3292 KB Output is correct
18 Correct 98 ms 4260 KB Output is correct
19 Correct 89 ms 4136 KB Output is correct
20 Correct 90 ms 4140 KB Output is correct
21 Correct 96 ms 4088 KB Output is correct
22 Correct 196 ms 7360 KB Output is correct
23 Correct 18 ms 1100 KB Output is correct
24 Correct 65 ms 2764 KB Output is correct
25 Correct 3 ms 324 KB Output is correct
26 Correct 17 ms 1016 KB Output is correct

Subtask #6
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 4 ms 468 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 3 ms 488 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 5 ms 468 KB Output is correct
17 Correct 121 ms 3292 KB Output is correct
18 Correct 98 ms 4260 KB Output is correct
19 Correct 89 ms 4136 KB Output is correct
20 Correct 90 ms 4140 KB Output is correct
21 Correct 96 ms 4088 KB Output is correct
22 Correct 196 ms 7360 KB Output is correct
23 Correct 18 ms 1100 KB Output is correct
24 Correct 65 ms 2764 KB Output is correct
25 Correct 3 ms 324 KB Output is correct
26 Correct 17 ms 1016 KB Output is correct
27 Correct 6 ms 820 KB Output is correct
28 Correct 556 ms 15632 KB Output is correct
29 Correct 889 ms 21560 KB Output is correct
30 Correct 672 ms 19672 KB Output is correct
31 Correct 686 ms 19616 KB Output is correct
32 Correct 731 ms 21780 KB Output is correct
33 Correct 717 ms 19768 KB Output is correct
34 Correct 689 ms 19672 KB Output is correct
35 Correct 232 ms 8464 KB Output is correct
36 Correct 737 ms 21040 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 13604 KB Output is correct
2 Correct 115 ms 13600 KB Output is correct
3 Correct 138 ms 15644 KB Output is correct
4 Correct 134 ms 16012 KB Output is correct
5 Correct 201 ms 20028 KB Output is correct
6 Correct 192 ms 20240 KB Output is correct
7 Correct 218 ms 20264 KB Output is correct
8 Correct 203 ms 20224 KB Output is correct
9 Correct 220 ms 19996 KB Output is correct
10 Correct 177 ms 12588 KB Output is correct
11 Correct 329 ms 24920 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 84 ms 13608 KB Output is correct
19 Correct 85 ms 13604 KB Output is correct
20 Correct 88 ms 13564 KB Output is correct
21 Correct 85 ms 13608 KB Output is correct
22 Correct 238 ms 19560 KB Output is correct
23 Correct 369 ms 24940 KB Output is correct
24 Correct 364 ms 25388 KB Output is correct

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 416 ms 47656 KB Output is correct
2 Correct 527 ms 57308 KB Output is correct
3 Correct 86 ms 13604 KB Output is correct
4 Correct 83 ms 13500 KB Output is correct
5 Execution timed out 1087 ms 65496 KB Time limit exceeded
6 Halted 0 ms 0 KB -