oj.uz

Submission #630653

# Submission time Handle Problem Language Result Execution time Memory
630653 2022-08-16T20:16:28 Z CSQ31 Catfish Farm (IOI22_fish) C++17
12 / 100
 374 ms 87376 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(Y[id] != st[i][j])continue;
				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[0][i][j]);
			}
			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[1][i][j]);
				mx = max(mx,dp[1][i-1][ptr] + pre[1][i][j]);
			}
			dp[1][i][j] = max(dp[1][i][j],mx - pre[1][i][j]);	
		}
		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]);
		}
	}
  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
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 49316 KB Output is correct
2 Correct 134 ms 54180 KB Output is correct
3 Correct 41 ms 37672 KB Output is correct
4 Correct 42 ms 37708 KB Output is correct
5 Correct 300 ms 87376 KB Output is correct
6 Correct 374 ms 83776 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 18572 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 37648 KB Output is correct
2 Correct 43 ms 37740 KB Output is correct
3 Correct 86 ms 38660 KB Output is correct
4 Correct 69 ms 39760 KB Output is correct
5 Correct 114 ms 43320 KB Output is correct
6 Correct 105 ms 43884 KB Output is correct
7 Correct 108 ms 44148 KB Output is correct
8 Correct 115 ms 44164 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 18516 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 18516 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 18516 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 37648 KB Output is correct
2 Correct 43 ms 37740 KB Output is correct
3 Correct 86 ms 38660 KB Output is correct
4 Correct 69 ms 39760 KB Output is correct
5 Correct 114 ms 43320 KB Output is correct
6 Correct 105 ms 43884 KB Output is correct
7 Correct 108 ms 44148 KB Output is correct
8 Correct 115 ms 44164 KB Output is correct
9 Incorrect 122 ms 51704 KB 1st lines differ - on the 1st token, expected: '99999', found: '66666'
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 49316 KB Output is correct
2 Correct 134 ms 54180 KB Output is correct
3 Correct 41 ms 37672 KB Output is correct
4 Correct 42 ms 37708 KB Output is correct
5 Correct 300 ms 87376 KB Output is correct
6 Correct 374 ms 83776 KB Output is correct
7 Incorrect 10 ms 18572 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
8 Halted 0 ms 0 KB -