oj.uz

Submission #630558

# Submission time Handle Problem Language Result Execution time Memory
630558 2022-08-16T14:11:34 Z CSQ31 Catfish Farm (IOI22_fish) C++17
0 / 100
 1000 ms 56700 KB 
#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;
		/*
		mx = INF;
		ptr = -1;
		for(int j=0;j<cnt[i];j++){
			while(ptr+1 < cnt[i-2] && st[i-2][ptr+1] <= st[i][j]){
				ptr++;
				mx = max(mx,dp[0][i-2][ptr]);
				mx = max(mx,dp[1][i-2][ptr]);
			}
			dp[0][i][j] = max(dp[0][i][j],mx + pre[0][i][j]);
		}*/
		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][ptr],dp[1][i-2][ptr]);
					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 1057 ms 49308 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 37676 KB Output is correct
2 Correct 42 ms 37708 KB Output is correct
3 Incorrect 81 ms 38652 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '20888171954393'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18516 KB Output is correct
2 Correct 9 ms 18516 KB Output is correct
3 Correct 9 ms 18516 KB Output is correct
4 Correct 10 ms 18516 KB Output is correct
5 Correct 10 ms 18516 KB Output is correct
6 Correct 10 ms 18516 KB Output is correct
7 Correct 10 ms 18536 KB Output is correct
8 Correct 9 ms 18560 KB Output is correct
9 Incorrect 10 ms 18520 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '214837477243'
10 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 9 ms 18516 KB Output is correct
3 Correct 9 ms 18516 KB Output is correct
4 Correct 10 ms 18516 KB Output is correct
5 Correct 10 ms 18516 KB Output is correct
6 Correct 10 ms 18516 KB Output is correct
7 Correct 10 ms 18536 KB Output is correct
8 Correct 9 ms 18560 KB Output is correct
9 Incorrect 10 ms 18520 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '214837477243'
10 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 9 ms 18516 KB Output is correct
3 Correct 9 ms 18516 KB Output is correct
4 Correct 10 ms 18516 KB Output is correct
5 Correct 10 ms 18516 KB Output is correct
6 Correct 10 ms 18516 KB Output is correct
7 Correct 10 ms 18536 KB Output is correct
8 Correct 9 ms 18560 KB Output is correct
9 Incorrect 10 ms 18520 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '214837477243'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 37676 KB Output is correct
2 Correct 42 ms 37708 KB Output is correct
3 Incorrect 81 ms 38652 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '20888171954393'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

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