Submission #629895

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
629895	2022-08-15T10:33:08 Z	jh05013	Catfish Farm (IOI22_fish)	C++17	81 / 100	1000 ms	138756 KB

fish

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
void OJize(){cin.tie(NULL);ios_base::sync_with_stdio(false);}
 
typedef long long ll;
const int IINF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define sz(X) (int)((X).size())
#define entire(X) X.begin(),X.end()
template <class T1, class T2>ostream&operator<<(ostream &os,pair<T1,T2>const&x){os<<'('<<x.first<<", "<<x.second<<')';return os;}
template <class Ch, class Tr, class Container>basic_ostream<Ch,Tr>&operator<<(basic_ostream<Ch,Tr>&os,Container const&x){os<<"[ ";for(auto&y:x)os<<y<<" ";return os<<"]";}
 
template <typename T>
struct Compress{
	int n; vector<T> arr;
	void add(T x){arr.push_back(x); n++;}
	void init(){sort(entire(arr));}
	int lb(T x){return lower_bound(entire(arr), x) - arr.begin();}
	int ub(T x){return upper_bound(entire(arr), x) - arr.begin();}
};
 
// NOTE: this is not a "sparse table" related to
// binary lifting, it's literally an array which is sparse!!
template<typename T>
struct SparseArray{
	// not actually sparse yet!!
	int n, L;
	vector<int> idxs;
	Compress<int> C;
	vector<T> val, sum, prefm, sufm;
	
	SparseArray(int N): n{N} {}
 
	map<int, T> M;
	void write(int i, T x){M[i] = x;}
	void init(){
		L = sz(M);
		if(!L) return;
		sum.resize(L), prefm.resize(L), sufm.resize(L);
		for(auto [i, x]: M) C.add(i), val.push_back(x);
		C.init();
		sum[0] = prefm[0] = val[0];
		for(int i=1; i<L; i++){
			sum[i] = sum[i-1]+val[i];
			prefm[i] = max(prefm[i-1], val[i]);
		}
		idxs = C.arr;
		sufm[L-1] = val[L-1];
		for(int i=L-2; i>=0; i--)
			sufm[i] = max(sufm[i+1], val[i]);
	}
 
	T operator[](int i){
		int idx = C.lb(i);
		if(idx == L || C.arr[idx] != i) return 0;
		return val[idx];
	}
	T prefsum(int i){
		i = C.ub(i)-1;
		return i>=0? sum[i] : (T)0;
	}
	T getsum(int l, int r){return prefsum(r) - prefsum(l);}
	T allmax(){return prefm.back();}
	T prefmax(int i){
		i = C.ub(i)-1;
		return i>=0? prefm[i] : (T)0;
	}
	T sufmax(int i){
		i = C.lb(i);
		return i<L? sufm[i] : (T)0;
	}
};
 
ll max_weights(int L, int n,
vector<int> X, vector<int> Y, vector<int> W){
	vector<SparseArray<ll>> grid(L, SparseArray<ll>(L+1));
	for(int i=0; i<L; i++)
		grid[i].write(0, 0), grid[i].write(L, 0);
	for(int i=0; i<n; i++) grid[X[i]].write(Y[i], (ll)W[i]);
	for(auto &A: grid) A.init();
 
	SparseArray<ll> dinc(L+1), ddec(L+1);
	dinc.init(); ddec.init();
	// column _,
	// last column height j,
	// next will increase/decrease
	for(int i=1; i<L; i++){
		SparseArray<ll> ndinc(L+1), nddec(L+1);
		SparseArray<ll> incmaxer(L+1), decmaxer(L+1);
		for(int y0: grid[i-1].idxs){
			incmaxer.write(y0, dinc[y0] - grid[i-1].prefsum(y0-1));
			decmaxer.write(y0, ddec[y0] + grid[i].prefsum(y0-1));
		}
		incmaxer.init(), decmaxer.init();
		for(int y: grid[i].idxs){
			ll incy = 0, decy = 0;
			if(y == 0) incy = decy = ddec[0];
			if(y == L) incy = decy = max(ddec[0], dinc[L]);
			
			ll incmax = grid[i-1].prefsum(y-1) + incmaxer.prefmax(y-1);
			incy = max(incy, incmax);
			if(y == L) decy = max(decy, incmax);
			ll decmax = -grid[i].prefsum(y-1) + decmaxer.sufmax(y+1);
			decy = max(decy, decmax);
			ndinc.write(y, incy);
			nddec.write(y, decy);
		}
		ndinc.init(), nddec.init();
		dinc = ndinc, ddec = nddec;
	}
 
	return max(dinc.allmax(), ddec.allmax());
}
 
#ifdef jh
int main(){OJize();
	int n; cin>>n;
	vector<int> X, Y, W;
	for(int i=0; i<n; i++) for(int j=0; j<n; j++){
		int x; cin>>x;
		if(x){
			X.push_back(j);
			Y.push_back(n-1-i);
			W.push_back(x);
		}
	}
	cout << max_weights(n, sz(X), X, Y, W);
}
#endif

Subtask #1
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	345 ms	74188 KB	Output is correct
2	Correct	412 ms	85476 KB	Output is correct
3	Correct	255 ms	51916 KB	Output is correct
4	Correct	256 ms	51912 KB	Output is correct
5	Execution timed out	1073 ms	128520 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #2
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	597 ms	117424 KB	Output is correct
3	Correct	730 ms	138756 KB	Output is correct
4	Correct	322 ms	74192 KB	Output is correct
5	Correct	409 ms	85528 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	284 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	235 ms	51936 KB	Output is correct
11	Correct	250 ms	51832 KB	Output is correct
12	Correct	380 ms	91104 KB	Output is correct
13	Correct	469 ms	106340 KB	Output is correct
14	Correct	349 ms	81732 KB	Output is correct
15	Correct	412 ms	90976 KB	Output is correct
16	Correct	339 ms	81768 KB	Output is correct
17	Correct	382 ms	90856 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	249 ms	51936 KB	Output is correct
2	Correct	231 ms	51876 KB	Output is correct
3	Correct	236 ms	47992 KB	Output is correct
4	Correct	239 ms	52812 KB	Output is correct
5	Correct	368 ms	54400 KB	Output is correct
6	Correct	273 ms	54344 KB	Output is correct
7	Correct	273 ms	54312 KB	Output is correct
8	Correct	286 ms	54312 KB	Output is correct

Subtask #4
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 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	3 ms	724 KB	Output is correct
11	Correct	2 ms	340 KB	Output is correct
12	Correct	4 ms	468 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	2 ms	468 KB	Output is correct

Subtask #5
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 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	3 ms	724 KB	Output is correct
11	Correct	2 ms	340 KB	Output is correct
12	Correct	4 ms	468 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	2 ms	468 KB	Output is correct
15	Correct	1 ms	468 KB	Output is correct
16	Correct	4 ms	596 KB	Output is correct
17	Correct	76 ms	6384 KB	Output is correct
18	Correct	73 ms	6704 KB	Output is correct
19	Correct	70 ms	6528 KB	Output is correct
20	Correct	64 ms	6532 KB	Output is correct
21	Correct	65 ms	6472 KB	Output is correct
22	Correct	153 ms	12752 KB	Output is correct
23	Correct	12 ms	1572 KB	Output is correct
24	Correct	42 ms	4456 KB	Output is correct
25	Correct	3 ms	596 KB	Output is correct
26	Correct	11 ms	1536 KB	Output is correct

Subtask #6
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 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	3 ms	724 KB	Output is correct
11	Correct	2 ms	340 KB	Output is correct
12	Correct	4 ms	468 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	2 ms	468 KB	Output is correct
15	Correct	1 ms	468 KB	Output is correct
16	Correct	4 ms	596 KB	Output is correct
17	Correct	76 ms	6384 KB	Output is correct
18	Correct	73 ms	6704 KB	Output is correct
19	Correct	70 ms	6528 KB	Output is correct
20	Correct	64 ms	6532 KB	Output is correct
21	Correct	65 ms	6472 KB	Output is correct
22	Correct	153 ms	12752 KB	Output is correct
23	Correct	12 ms	1572 KB	Output is correct
24	Correct	42 ms	4456 KB	Output is correct
25	Correct	3 ms	596 KB	Output is correct
26	Correct	11 ms	1536 KB	Output is correct
27	Correct	13 ms	2044 KB	Output is correct
28	Correct	474 ms	30072 KB	Output is correct
29	Correct	668 ms	42128 KB	Output is correct
30	Correct	533 ms	40580 KB	Output is correct
31	Correct	569 ms	40408 KB	Output is correct
32	Correct	578 ms	42116 KB	Output is correct
33	Correct	478 ms	40612 KB	Output is correct
34	Correct	493 ms	40540 KB	Output is correct
35	Correct	153 ms	16844 KB	Output is correct
36	Correct	533 ms	41700 KB	Output is correct

Subtask #7
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	249 ms	51936 KB	Output is correct
2	Correct	231 ms	51876 KB	Output is correct
3	Correct	236 ms	47992 KB	Output is correct
4	Correct	239 ms	52812 KB	Output is correct
5	Correct	368 ms	54400 KB	Output is correct
6	Correct	273 ms	54344 KB	Output is correct
7	Correct	273 ms	54312 KB	Output is correct
8	Correct	286 ms	54312 KB	Output is correct
9	Correct	373 ms	62028 KB	Output is correct
10	Correct	191 ms	32284 KB	Output is correct
11	Correct	405 ms	64492 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 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	1 ms	212 KB	Output is correct
18	Correct	228 ms	51848 KB	Output is correct
19	Correct	240 ms	51920 KB	Output is correct
20	Correct	236 ms	51904 KB	Output is correct
21	Correct	229 ms	51916 KB	Output is correct
22	Correct	381 ms	63160 KB	Output is correct
23	Correct	512 ms	74780 KB	Output is correct
24	Correct	490 ms	75484 KB	Output is correct

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	345 ms	74188 KB	Output is correct
2	Correct	412 ms	85476 KB	Output is correct
3	Correct	255 ms	51916 KB	Output is correct
4	Correct	256 ms	51912 KB	Output is correct
5	Execution timed out	1073 ms	128520 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Submission #629895

Compilation message