oj.uz

답안 #838097

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
838097 2023-08-26T08:34:38 Z MohamedAhmed04 별자리 3 (JOI20_constellation3) C++14
0 / 100
 2 ms 4948 KB 
#include <bits/stdc++.h>

using namespace std ;

const int MAX = 2e5 + 10 ;

int arr[MAX] ;
int n , m ;

vector< pair<int , int> >vp[MAX] ;

long long maxdp[MAX] ;
long long Max = 0 ;

int L[MAX] , R[MAX] ;

void solve(int l , int r)
{
	if(l > r)
		return ;
	int idx = -1 ;
	for(int i = l , j = r ; i <= j ; ++i , --j)
	{
		if(L[i] <= l && R[i] >= r)
		{
			idx = i ;
			break ;
		}
		if(L[j] <= l && R[j] >= r)
		{
			idx = j ;
			break ;
		}
	}
	assert(idx != -1) ;
	long long curMax = 0 ; 
	for(int i = 1 ; i <= n ; ++i)
	{
		if(i >= l && i <= r)
			continue ;
		curMax = max(curMax , maxdp[i]) ;
	}
	for(int i = l ; i <= r ; ++i)
	{
		while(vp[i].size() && vp[i].back().first <= arr[idx])
		{
			pair<int , int>p = vp[i].back() ;
			vp[i].pop_back() ;
			maxdp[i] = max(maxdp[i] , curMax + p.second) ;
			Max = max(Max , maxdp[i]) ;
		}
	}
	solve(l , idx-1) , solve(idx+1 , r) ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 1 ; i <= n ; ++i)
		cin>>arr[i] , arr[i] = n-arr[i] ;
	cin>>m ;
	long long ans = 0 ;
	for(int i = 0 ; i < m ; ++i)
	{
		int i2 , j2 , x ;
		cin>>i2>>j2>>x ;
		vp[i2].emplace_back(n-j2+1 , x) ;
		ans += x ;
	}
	for(int i = 1 ; i <= n ; ++i)
		sort(vp[i].begin() , vp[i].end()) , reverse(vp[i].begin() , vp[i].end()) ;
	stack<int>s ;
	for(int i = 1 ; i <= n ; ++i)
	{
		L[i] = 1 ;
		while(s.size() && arr[i] < arr[s.top()])
			s.pop() ;
		if(s.size())
			L[i] = s.top() + 1 ;
		s.push(i) ;
	}
	while(s.size())
		s.pop() ;
	for(int i = n ; i >= 1 ; --i)
	{
		R[i] = n ;
		while(s.size() && arr[i] <= arr[s.top()])
			s.pop() ;
		if(s.size())
			R[i] = s.top() - 1 ;
		s.push(i) ;
	}
	solve(1 , n) ;
	ans -= Max ;
	return cout<<ans<<"\n" , 0 ;
}

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -