oj.uz

Submission #629429

# Submission time Handle Problem Language Result Execution time Memory
629429 2022-08-14T13:36:55 Z handlename Catfish Farm (IOI22_fish) C++17
15 / 100
 392 ms 65612 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]));
				if (i>=2){
					maxi=max(maxi,dp2[i-2][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=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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 31552 KB Output is correct
2 Correct 136 ms 34908 KB Output is correct
3 Correct 41 ms 23764 KB Output is correct
4 Correct 38 ms 23760 KB Output is correct
5 Correct 342 ms 59092 KB Output is correct
6 Incorrect 392 ms 65612 KB 1st lines differ - on the 1st token, expected: '300000000000000', found: '440713308486144'
7 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 189 ms 38384 KB Output is correct
3 Correct 214 ms 42816 KB Output is correct
4 Correct 114 ms 31692 KB Output is correct
5 Correct 126 ms 34924 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 39 ms 23644 KB Output is correct
11 Correct 46 ms 23772 KB Output is correct
12 Correct 116 ms 31728 KB Output is correct
13 Correct 134 ms 34916 KB Output is correct
14 Correct 115 ms 32480 KB Output is correct
15 Correct 125 ms 32744 KB Output is correct
16 Correct 128 ms 32396 KB Output is correct
17 Correct 124 ms 34564 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 23680 KB Output is correct
2 Correct 40 ms 23756 KB Output is correct
3 Correct 73 ms 26208 KB Output is correct
4 Correct 64 ms 26316 KB Output is correct
5 Correct 114 ms 31352 KB Output is correct
6 Correct 95 ms 31352 KB Output is correct
7 Correct 95 ms 31344 KB Output is correct
8 Correct 105 ms 31332 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 7 ms 9684 KB Output is correct
7 Correct 5 ms 9588 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9720 KB Output is correct
10 Correct 7 ms 9988 KB Output is correct
11 Incorrect 6 ms 9684 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '280313907877'
12 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 7 ms 9684 KB Output is correct
7 Correct 5 ms 9588 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9720 KB Output is correct
10 Correct 7 ms 9988 KB Output is correct
11 Incorrect 6 ms 9684 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '280313907877'
12 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 7 ms 9684 KB Output is correct
7 Correct 5 ms 9588 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9720 KB Output is correct
10 Correct 7 ms 9988 KB Output is correct
11 Incorrect 6 ms 9684 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '280313907877'
12 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 23680 KB Output is correct
2 Correct 40 ms 23756 KB Output is correct
3 Correct 73 ms 26208 KB Output is correct
4 Correct 64 ms 26316 KB Output is correct
5 Correct 114 ms 31352 KB Output is correct
6 Correct 95 ms 31352 KB Output is correct
7 Correct 95 ms 31344 KB Output is correct
8 Correct 105 ms 31332 KB Output is correct
9 Correct 111 ms 34928 KB Output is correct
10 Correct 100 ms 27920 KB Output is correct
11 Correct 181 ms 46356 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 5 ms 9640 KB Output is correct
15 Correct 5 ms 9692 KB Output is correct
16 Correct 5 ms 9684 KB Output is correct
17 Correct 4 ms 9684 KB Output is correct
18 Correct 40 ms 23764 KB Output is correct
19 Correct 44 ms 23688 KB Output is correct
20 Correct 40 ms 23680 KB Output is correct
21 Correct 38 ms 23676 KB Output is correct
22 Incorrect 150 ms 36004 KB 1st lines differ - on the 1st token, expected: '45561826463480', found: '47726682653287'
23 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 31552 KB Output is correct
2 Correct 136 ms 34908 KB Output is correct
3 Correct 41 ms 23764 KB Output is correct
4 Correct 38 ms 23760 KB Output is correct
5 Correct 342 ms 59092 KB Output is correct
6 Incorrect 392 ms 65612 KB 1st lines differ - on the 1st token, expected: '300000000000000', found: '440713308486144'
7 Halted 0 ms 0 KB -