Submission #630561

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
630561	2022-08-16T14:13:07 Z	CSQ31	Catfish Farm (IOI22_fish)	C++17	9 / 100	1000 ms	56800 KB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
#define fi first
#define se second
#define sz(a) (int)(a.size())
//0 -> previous is lower
//1 -> previous is higher
const int MAXN = 111111;
vector<int>st[MAXN];
vector<pii>fish[MAXN];
vector<ll>dp[2][MAXN],pre[3][MAXN];
int cnt[MAXN];
const ll INF = -1e17;
long long max_weights(int n, int m, vector<int> X, vector<int> Y,vector<int> W) {
	for(int i=0;i<m;i++){
		X[i]++;
		Y[i]++;
		fish[X[i]].push_back({Y[i],i});
	}
	for(int i=0;i<=n;i++){
		vector<pii>f;
		st[i].push_back(0);
		if(i){
			for(auto x:fish[i-1]){
				st[i].push_back(x.fi);
				f.push_back(x);
			}
		}
		for(auto x:fish[i]){
			st[i].push_back(x.fi);
			f.push_back(x);
		}
		for(auto x:fish[i+1]){
			st[i].push_back(x.fi);
			f.push_back(x);
		}
		sort(st[i].begin(),st[i].end());
		sort(f.begin(),f.end());
		st[i].resize(unique(st[i].begin(),st[i].end()) - st[i].begin());
		cnt[i] = st[i].size();
		for(int k=0;k<3;k++)pre[k][i].assign(cnt[i],0);
		for(int k=0;k<2;k++)dp[k][i].assign(cnt[i],INF);
		int ptr = -1;
		for(int j=0;j<cnt[i];j++){
			while(ptr+1 < sz(f) && f[ptr+1].fi <= st[i][j]){
				ptr++;
				int id = f[ptr].se;
				if(X[id] == i-1)pre[0][i][j]+=W[id];
				if(X[id] == i  )pre[1][i][j]+=W[id];
				if(X[id] == i+1)pre[2][i][j]+=W[id];
			}
		}
		for(int k=0;k<3;k++){
			for(int j=1;j<cnt[i];j++)pre[k][i][j]+=pre[k][i][j-1];
		}
	}
	dp[0][0][0] = 0;
	for(int i=1;i<=n;i++){
		ll mx = INF;
		int ptr = -1;
		for(int j=0;j<cnt[i];j++){
			while(ptr+1<cnt[i-1] && st[i-1][ptr+1] <= st[i][j]){
				ptr++;
				mx = max(mx,dp[0][i-1][ptr] - pre[1][i-1][ptr]);
			}
			dp[0][i][j] = max(dp[0][i][j],mx + pre[0][i][j]);
		}
		mx = INF;
		ptr = cnt[i-1];
		for(int j=cnt[i]-1;j>=0;j--){
			while(ptr-1>=0 && st[i-1][ptr-1] >= st[i][j]){
				ptr--;
				mx = max(mx,dp[0][i-1][ptr] + pre[2][i-1][ptr]);
				mx = max(mx,dp[1][i-1][ptr] + pre[2][i-1][ptr]);
			}
			dp[1][i][j] = max(dp[1][i][j],mx - pre[1][i][j]);	
		}
		/*
		if(i>=2){
			sum = 0;
			mx = INF;
			for(int j=0;j<=n;j++){
				sum+=f[i-1][j];
				mx = max(mx,dp[0][i-2][j]);
				mx = max(mx,dp[1][i-2][j]);
				dp[0][i][j] = max(dp[0][i][j],mx+sum);
			}
			
		}*/
		if(i<2)continue;
		for(int j=0;j<cnt[i];j++){
			for(int k=0;k<cnt[i-2];k++){
				if(st[i-2][k] <= st[i][j]){
					mx = max(dp[0][i-2][k],dp[1][i-2][k]);
					dp[0][i][j] = max(dp[0][i][j],mx+pre[0][i][j]);
				}
				
			}
			
		}
	}
  ll ans = 0;
  for(ll x:dp[0][n])ans = max(ans,x);
  for(ll x:dp[1][n])ans = max(ans,x);
  return ans;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	18516 KB	Output is correct
2	Execution timed out	1084 ms	56800 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	41 ms	37720 KB	Output is correct
2	Correct	47 ms	37680 KB	Output is correct
3	Correct	104 ms	38676 KB	Output is correct
4	Correct	70 ms	39700 KB	Output is correct
5	Correct	136 ms	43104 KB	Output is correct
6	Correct	112 ms	43200 KB	Output is correct
7	Correct	106 ms	43196 KB	Output is correct
8	Correct	107 ms	43128 KB	Output is correct

Subtask #4
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	18516 KB	Output is correct
2	Correct	10 ms	18556 KB	Output is correct
3	Correct	10 ms	18552 KB	Output is correct
4	Correct	12 ms	18508 KB	Output is correct
5	Correct	12 ms	18516 KB	Output is correct
6	Correct	10 ms	18492 KB	Output is correct
7	Correct	11 ms	18516 KB	Output is correct
8	Correct	12 ms	18516 KB	Output is correct
9	Correct	12 ms	18516 KB	Output is correct
10	Correct	11 ms	18772 KB	Output is correct
11	Incorrect	10 ms	18660 KB	1st lines differ - on the 1st token, expected: '278622587073', found: '278441359083'
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	18516 KB	Output is correct
2	Correct	10 ms	18556 KB	Output is correct
3	Correct	10 ms	18552 KB	Output is correct
4	Correct	12 ms	18508 KB	Output is correct
5	Correct	12 ms	18516 KB	Output is correct
6	Correct	10 ms	18492 KB	Output is correct
7	Correct	11 ms	18516 KB	Output is correct
8	Correct	12 ms	18516 KB	Output is correct
9	Correct	12 ms	18516 KB	Output is correct
10	Correct	11 ms	18772 KB	Output is correct
11	Incorrect	10 ms	18660 KB	1st lines differ - on the 1st token, expected: '278622587073', found: '278441359083'
12	Halted	0 ms	0 KB	-

Subtask #6
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	18516 KB	Output is correct
2	Correct	10 ms	18556 KB	Output is correct
3	Correct	10 ms	18552 KB	Output is correct
4	Correct	12 ms	18508 KB	Output is correct
5	Correct	12 ms	18516 KB	Output is correct
6	Correct	10 ms	18492 KB	Output is correct
7	Correct	11 ms	18516 KB	Output is correct
8	Correct	12 ms	18516 KB	Output is correct
9	Correct	12 ms	18516 KB	Output is correct
10	Correct	11 ms	18772 KB	Output is correct
11	Incorrect	10 ms	18660 KB	1st lines differ - on the 1st token, expected: '278622587073', found: '278441359083'
12	Halted	0 ms	0 KB	-

Subtask #7
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	41 ms	37720 KB	Output is correct
2	Correct	47 ms	37680 KB	Output is correct
3	Correct	104 ms	38676 KB	Output is correct
4	Correct	70 ms	39700 KB	Output is correct
5	Correct	136 ms	43104 KB	Output is correct
6	Correct	112 ms	43200 KB	Output is correct
7	Correct	106 ms	43196 KB	Output is correct
8	Correct	107 ms	43128 KB	Output is correct
9	Correct	114 ms	50984 KB	Output is correct
10	Correct	88 ms	32820 KB	Output is correct
11	Correct	173 ms	47136 KB	Output is correct
12	Correct	10 ms	18516 KB	Output is correct
13	Correct	11 ms	18464 KB	Output is correct
14	Correct	13 ms	18456 KB	Output is correct
15	Correct	10 ms	18564 KB	Output is correct
16	Correct	11 ms	18464 KB	Output is correct
17	Correct	10 ms	18500 KB	Output is correct
18	Correct	42 ms	37740 KB	Output is correct
19	Correct	42 ms	37624 KB	Output is correct
20	Correct	41 ms	37708 KB	Output is correct
21	Correct	42 ms	37724 KB	Output is correct
22	Incorrect	179 ms	48796 KB	1st lines differ - on the 1st token, expected: '45561826463480', found: '45409419542258'
23	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

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

Submission #630561

Compilation message