Submission #828567

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
828567	2023-08-17T11:23:49 Z	ttamx	Catfish Farm (IOI22_fish)	C++17	61 / 100	1000 ms	2097152 KB

fish

#include "fish.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=1e5+5;
const ll inf=1e18;

int n,m;
vector<vector<ll>> w;
vector<vector<vector<ll>>> dp;
ll suff[N];
ll val[N];

long long max_weights(int _n,int _m,vector<int> X,vector<int> Y,vector<int> W) {
	n=_n,m=_m;
	int mxy=0;
	for(auto x:Y)mxy=max(mxy,x+1);
	w=vector<vector<ll>>(n+5,vector<ll>(mxy+5));
	dp=vector<vector<vector<ll>>>(n+5,vector<vector<ll>>(mxy+5,vector<ll>(2)));
	for(int i=0;i<m;i++)w[X[i]+1][Y[i]+1]=W[i];
	for(int i=1;i<=n;i++)for(int j=1;j<=mxy;j++)w[i][j]+=w[i][j-1];
	for(int i=1;i<=n;i++)for(int j=0;j<=mxy;j++)dp[i][j][0]=dp[i][j][1]=-inf;
	for(int i=1;i<=n;i++){
		if(i>=2)for(int j=mxy;j>=0;j--)suff[j]=max(suff[j+1],dp[i-2][j][1]);
		ll tmp=-inf,tmp2=-inf;
		for(int j=0;j<=mxy;j++){
			tmp=max(tmp,dp[i-1][j][0]-w[i][j]-w[i-1][j]);
			dp[i][j][0]=w[i-1][j]+tmp+w[i+1][j];
			if(i>=2){
				tmp2=max(tmp2,dp[i-2][j][0]-w[i-1][j]);
				dp[i][j][0]=max(dp[i][j][0],w[i-1][j]+tmp+w[i+1][j]);
				dp[i][j][0]=max(dp[i][j][0],suff[j]+w[i+1][j]);
			}
		}
		tmp=-inf;
		for(int j=mxy;j>=0;j--){
			tmp=max(tmp,dp[i-1][j][1]);
			dp[i][j][1]=tmp-w[i][j]+w[i+1][j];
			dp[i][j][1]=max(dp[i][j][1],dp[i][j][0]);
		}
	}
	ll ans=0;
	for(int i=0;i<=mxy;i++)ans=max(ans,dp[n][i][1]);
	return ans;
}

Subtask #1
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1088 ms	2097152 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Runtime error	715 ms	2097152 KB	Execution killed with signal 9
3	Halted	0 ms	0 KB	-

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	47 ms	45652 KB	Output is correct
2	Correct	48 ms	45644 KB	Output is correct
3	Correct	56 ms	43340 KB	Output is correct
4	Correct	57 ms	47148 KB	Output is correct
5	Correct	72 ms	49596 KB	Output is correct
6	Correct	71 ms	49020 KB	Output is correct
7	Correct	73 ms	49624 KB	Output is correct
8	Correct	72 ms	49520 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	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	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	312 KB	Output is correct
10	Correct	1 ms	596 KB	Output is correct
11	Correct	1 ms	468 KB	Output is correct
12	Correct	1 ms	576 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 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	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	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	312 KB	Output is correct
10	Correct	1 ms	596 KB	Output is correct
11	Correct	1 ms	468 KB	Output is correct
12	Correct	1 ms	576 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	468 KB	Output is correct
15	Correct	6 ms	6068 KB	Output is correct
16	Correct	1 ms	724 KB	Output is correct
17	Correct	16 ms	8024 KB	Output is correct
18	Correct	17 ms	7972 KB	Output is correct
19	Correct	17 ms	7996 KB	Output is correct
20	Correct	15 ms	7892 KB	Output is correct
21	Correct	13 ms	5076 KB	Output is correct
22	Correct	26 ms	9784 KB	Output is correct
23	Correct	8 ms	6484 KB	Output is correct
24	Correct	12 ms	7324 KB	Output is correct
25	Correct	1 ms	828 KB	Output is correct
26	Correct	8 ms	6484 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	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	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	312 KB	Output is correct
10	Correct	1 ms	596 KB	Output is correct
11	Correct	1 ms	468 KB	Output is correct
12	Correct	1 ms	576 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	468 KB	Output is correct
15	Correct	6 ms	6068 KB	Output is correct
16	Correct	1 ms	724 KB	Output is correct
17	Correct	16 ms	8024 KB	Output is correct
18	Correct	17 ms	7972 KB	Output is correct
19	Correct	17 ms	7996 KB	Output is correct
20	Correct	15 ms	7892 KB	Output is correct
21	Correct	13 ms	5076 KB	Output is correct
22	Correct	26 ms	9784 KB	Output is correct
23	Correct	8 ms	6484 KB	Output is correct
24	Correct	12 ms	7324 KB	Output is correct
25	Correct	1 ms	828 KB	Output is correct
26	Correct	8 ms	6484 KB	Output is correct
27	Correct	664 ms	566080 KB	Output is correct
28	Correct	86 ms	44856 KB	Output is correct
29	Correct	738 ms	578760 KB	Output is correct
30	Correct	717 ms	578708 KB	Output is correct
31	Correct	734 ms	578812 KB	Output is correct
32	Correct	86 ms	31568 KB	Output is correct
33	Correct	718 ms	578712 KB	Output is correct
34	Correct	765 ms	578796 KB	Output is correct
35	Correct	62 ms	35864 KB	Output is correct
36	Correct	711 ms	578696 KB	Output is correct

Subtask #7
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	47 ms	45652 KB	Output is correct
2	Correct	48 ms	45644 KB	Output is correct
3	Correct	56 ms	43340 KB	Output is correct
4	Correct	57 ms	47148 KB	Output is correct
5	Correct	72 ms	49596 KB	Output is correct
6	Correct	71 ms	49020 KB	Output is correct
7	Correct	73 ms	49624 KB	Output is correct
8	Correct	72 ms	49520 KB	Output is correct
9	Runtime error	695 ms	2097152 KB	Execution killed with signal 9
10	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1088 ms	2097152 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Submission #828567

Compilation message