oj.uz

Submission #629440

# Submission time Handle Problem Language Result Execution time Memory
629440 2022-08-14T13:42:09 Z handlename Catfish Farm (IOI22_fish) C++17
12 / 100
 423 ms 65484 KB 
#include <bits/stdc++.h>
//#include "fish.h"
using namespace std;
#define pb push_back
#define mp make_pair
 
vector<pair<int,long long> > arr[100005];
long long qry(int col,int height){ //prefixsum of col to height
	if (arr[col].empty()) return 0;
	pair<int,long long> lol=mp(height,1e18);
	int pos=upper_bound(arr[col].begin(),arr[col].end(),lol)-arr[col].begin();
	pos--;
	return arr[col][pos].second;
}
vector<long long> dp1[100005]; //col,height,increasing
vector<long long> dp2[100005]; //col,height,decreasing
vector<long long> whack[100005];
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]++;
		arr[x[i]].pb(mp(y[i],w[i]));
	}
	for (int i=1;i<=n;i++){
		arr[i].pb(mp(0,0));
		sort(arr[i].begin(),arr[i].end());
		for (int j=1;j<(int)arr[i].size();j++){
			arr[i][j].second+=arr[i][j-1].second;
		}
		for (auto j:arr[i]){
			whack[i].pb(j.first);
			//if (j.first>0) whack[i].pb(j.first-1);
			whack[i+1].pb(j.first);
			whack[i-1].pb(j.first);
		}
	}
	for (int i=0;i<=n;i++){
		sort(whack[i].begin(),whack[i].end());
		whack[i].erase(unique(whack[i].begin(),whack[i].end()),whack[i].end());
		for (int j=0;j<(int) whack[i].size();j++){
			dp1[i].pb(0);
			dp2[i].pb(0);
		}
	}
	for (int i=1;i<=n;i++){ //col
		long long maxi=0,id=0;
		for (int j=0;j<(int)whack[i].size();j++){
			int k=whack[i][j];
			while (id<(int)whack[i-1].size() && whack[i-1][id]<=k){
				maxi=max(maxi,dp1[i-1][id]-qry(i,whack[i-1][id])-qry(i-1,whack[i-1][id]));
				id++;
			}
			dp1[i][j]=maxi+qry(i-1,k)+qry(i+1,k);
		}
		/*
		for (int j=0;j<=n;j++){
			maxi=max(maxi,dp1[i-1][j]-qry(i,j)-qry(i-1,j));
			if (i>=2){
				maxi=max(maxi,dp2[i-2][j]-qry(i-1,j));
			}
			dp1[i][j]=maxi+qry(i-1,j)+qry(i+1,j);
		}
		*/
		
		if (i>=2){
			maxi=0;
			id=0;
			for (int j=0;j<(int)whack[i].size();j++){
				int k=whack[i][j];
				while (id<(int)whack[i-2].size() && whack[i-2][id]<=k){
					maxi=max(maxi,dp2[i-2][id]-qry(i-1,whack[i-2][id]));
					id++;
				}
				dp1[i][j]=maxi+qry(i-1,k)+qry(i+1,k);
			}
			maxi=0;
			id=whack[i-2].size()-1;
			for (int j=whack[i].size()-1;j>=0;j--){
				int k=whack[i][j];
				while (id>=0 && whack[i-2][id]>=k){
					maxi=max(maxi,dp2[i-2][id]);
					id--;
				}
				dp1[i][j]=max(dp1[i][j],maxi+qry(i+1,k));
			}
			/*
			for (int j=n;j>=0;j--){
				maxi=max(maxi,dp2[i-2][j]);
				dp1[i][j]=max(dp1[i][j],maxi+qry(i+1,j));
			}
			*/
		}
		
		maxi=0;
		id=whack[i-1].size()-1;
		for (int j=whack[i].size()-1;j>=0;j--){
			int k=whack[i][j];
			while (id>=0 && whack[i-1][id]>=k){
				maxi=max(maxi,dp2[i-1][id]);
				id--;
			}
			dp2[i][j]=maxi+qry(i+1,k)-qry(i,k);
		}
		/*
		for (int j=n;j>=0;j--){
			maxi=max(maxi,dp2[i-1][j]);
			dp2[i][j]=maxi+qry(i+1,j)-qry(i,j);
		}
		*/
		for (int j=0;j<(int)whack[i].size();j++){
			dp2[i][j]=max(dp2[i][j],dp1[i][j]);
		}
	}
	long long ans=0;
	for (int j=0;j<(int)dp2[n].size();j++){
		ans=max(ans,dp2[n][j]);
	}
	return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 31680 KB Output is correct
2 Correct 139 ms 34968 KB Output is correct
3 Correct 39 ms 23764 KB Output is correct
4 Correct 60 ms 23760 KB Output is correct
5 Correct 386 ms 59088 KB Output is correct
6 Correct 423 ms 65484 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 9684 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 39 ms 23764 KB Output is correct
2 Correct 45 ms 23768 KB Output is correct
3 Correct 71 ms 26212 KB Output is correct
4 Correct 65 ms 26264 KB Output is correct
5 Correct 110 ms 31432 KB Output is correct
6 Correct 111 ms 31428 KB Output is correct
7 Correct 110 ms 31308 KB Output is correct
8 Correct 100 ms 31352 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 9696 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 7 ms 9696 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 7 ms 9696 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 39 ms 23764 KB Output is correct
2 Correct 45 ms 23768 KB Output is correct
3 Correct 71 ms 26212 KB Output is correct
4 Correct 65 ms 26264 KB Output is correct
5 Correct 110 ms 31432 KB Output is correct
6 Correct 111 ms 31428 KB Output is correct
7 Correct 110 ms 31308 KB Output is correct
8 Correct 100 ms 31352 KB Output is correct
9 Incorrect 146 ms 34920 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 117 ms 31680 KB Output is correct
2 Correct 139 ms 34968 KB Output is correct
3 Correct 39 ms 23764 KB Output is correct
4 Correct 60 ms 23760 KB Output is correct
5 Correct 386 ms 59088 KB Output is correct
6 Correct 423 ms 65484 KB Output is correct
7 Incorrect 7 ms 9684 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
8 Halted 0 ms 0 KB -