oj.uz

답안 #1055994

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1055994 2024-08-13T07:00:47 Z parsadox2 메기 농장 (IOI22_fish) C++17
12 / 100
 84 ms 38648 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -