Submission #1055994

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1055994	2024-08-13T07:00:47 Z	parsadox2	Catfish Farm (IOI22_fish)	C++17	12 / 100	84 ms	38648 KB

fish

#include "fish.h"
#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

const int N = 1e5 + 10;
int n , m , sz[N];
vector <pair<int , int>> all[N];
vector <long long> dp[2][N];

long long max_weights(int nn , int mm , vector <int> X , vector <int> Y , vector <int> W)
{
	n = nn;
	m = mm;
	for(int i = 0 ; i < n ; i++)
		all[i].push_back({0 , 0});
	for(int i = 0 ; i < m ; i++)
		all[X[i]].push_back(make_pair(Y[i] , W[i]));
	for(int i = 0 ; i < n ; i++)
		all[i].push_back({n , 0});
	for(int i = 0 ; i < n ; i++)
	{
		sz[i] = all[i].size();
		dp[0][i].resize(sz[i] , 0);
		dp[1][i].resize(sz[i] , 0);
	}
	/*for(int i = 0 ; i < n ; i++)
	{
		cout << i << " : " << endl;
		for(auto u : all[i])
			cout << u.F << " " << u.S << endl;
	}*/
	long long ans = 0;
	for(int i = 1 ; i < n ; i++)
	{
		long long mx = 0;
		for(auto u : dp[0][i - 1])
			mx = max(mx , u);
		for(auto u : dp[1][i - 1])
			mx = max(mx , u);
		int pos = 0;
		long long val_down = 0;
		for(int j = 0 ; j < sz[i] ; j++)
		{
			//cout << i << " " << j << " " << pos << " WTF " << all[i - 1][pos].F << " " << all[i][j].F << endl;
			while(pos != sz[i - 1] && all[i - 1][pos].F < all[i][j].F)
			{
				val_down = max(val_down , dp[0][i - 1][pos]);
				val_down += all[i - 1][pos].S;
				pos++;
			}
			//cout << i << " " << j << " " << pos << " : " << val_down << endl;
			dp[0][i][j] = max(dp[0][i][j] , (max(mx , val_down)));
			dp[1][i][j] = max(dp[1][i][j] , (max(mx , val_down)));
		}
		long long val_up = 0;
		pos = sz[i - 1] - 1;
		for(int j = sz[i] - 1 ; j >= 0 ; j--)
		{
			while(pos >= 0 && all[i - 1][pos].F > all[i][j].F)
			{
				val_up = max(val_up , dp[1][i - 1][pos]);
				pos--;
			}
			val_up += all[i][j].S;
			dp[1][i][j] = max(dp[1][i][j] , val_up);
			ans = max(ans , dp[1][i][j]);
			ans = max(ans , dp[0][i][j]);
		}
		/*for(int j = 0 ; j < sz[i] ; j++)
			cout << i << " " << j << " ::: " << dp[0][i][j] << " " << dp[1][i][j] << endl;
		*/
	}
	return ans;
}

Subtask #1
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	21448 KB	Output is correct
2	Correct	30 ms	23664 KB	Output is correct
3	Correct	13 ms	17244 KB	Output is correct
4	Correct	16 ms	17240 KB	Output is correct
5	Correct	69 ms	37604 KB	Output is correct
6	Correct	84 ms	38648 KB	Output is correct

Subtask #2
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	7260 KB	Output is correct
2	Incorrect	41 ms	26664 KB	1st lines differ - on the 1st token, expected: '40604614618209', found: '56379036510698'
3	Halted	0 ms	0 KB	-

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	17240 KB	Output is correct
2	Correct	14 ms	17244 KB	Output is correct
3	Correct	26 ms	19544 KB	Output is correct
4	Correct	22 ms	19288 KB	Output is correct
5	Correct	37 ms	23240 KB	Output is correct
6	Correct	37 ms	22640 KB	Output is correct
7	Correct	73 ms	23124 KB	Output is correct
8	Correct	36 ms	23124 KB	Output is correct

Subtask #4
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7256 KB	Output is correct
2	Correct	2 ms	7344 KB	Output is correct
3	Correct	3 ms	7256 KB	Output is correct
4	Correct	4 ms	7260 KB	Output is correct
5	Correct	4 ms	7260 KB	Output is correct
6	Correct	3 ms	7256 KB	Output is correct
7	Correct	3 ms	7260 KB	Output is correct
8	Correct	4 ms	7260 KB	Output is correct
9	Incorrect	2 ms	7516 KB	1st lines differ - on the 1st token, expected: '216624184325', found: '219095659775'
10	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7256 KB	Output is correct
2	Correct	2 ms	7344 KB	Output is correct
3	Correct	3 ms	7256 KB	Output is correct
4	Correct	4 ms	7260 KB	Output is correct
5	Correct	4 ms	7260 KB	Output is correct
6	Correct	3 ms	7256 KB	Output is correct
7	Correct	3 ms	7260 KB	Output is correct
8	Correct	4 ms	7260 KB	Output is correct
9	Incorrect	2 ms	7516 KB	1st lines differ - on the 1st token, expected: '216624184325', found: '219095659775'
10	Halted	0 ms	0 KB	-

Subtask #6
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7256 KB	Output is correct
2	Correct	2 ms	7344 KB	Output is correct
3	Correct	3 ms	7256 KB	Output is correct
4	Correct	4 ms	7260 KB	Output is correct
5	Correct	4 ms	7260 KB	Output is correct
6	Correct	3 ms	7256 KB	Output is correct
7	Correct	3 ms	7260 KB	Output is correct
8	Correct	4 ms	7260 KB	Output is correct
9	Incorrect	2 ms	7516 KB	1st lines differ - on the 1st token, expected: '216624184325', found: '219095659775'
10	Halted	0 ms	0 KB	-

Subtask #7
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	17240 KB	Output is correct
2	Correct	14 ms	17244 KB	Output is correct
3	Correct	26 ms	19544 KB	Output is correct
4	Correct	22 ms	19288 KB	Output is correct
5	Correct	37 ms	23240 KB	Output is correct
6	Correct	37 ms	22640 KB	Output is correct
7	Correct	73 ms	23124 KB	Output is correct
8	Correct	36 ms	23124 KB	Output is correct
9	Correct	40 ms	22816 KB	Output is correct
10	Incorrect	31 ms	19144 KB	1st lines differ - on the 1st token, expected: '36454348383152', found: '36815854532776'
11	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	21448 KB	Output is correct
2	Correct	30 ms	23664 KB	Output is correct
3	Correct	13 ms	17244 KB	Output is correct
4	Correct	16 ms	17240 KB	Output is correct
5	Correct	69 ms	37604 KB	Output is correct
6	Correct	84 ms	38648 KB	Output is correct
7	Correct	2 ms	7260 KB	Output is correct
8	Incorrect	41 ms	26664 KB	1st lines differ - on the 1st token, expected: '40604614618209', found: '56379036510698'
9	Halted	0 ms	0 KB	-

Submission #1055994

Compilation message