oj.uz

Submission #262325

# Submission time Handle Problem Language Result Execution time Memory
262325 2020-08-12T16:19:11 Z easrui Constellation 3 (JOI20_constellation3) C++14
0 / 100
 5 ms 5120 KB 
#include <bits/stdc++.h>
#define va first
#define vb second
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef pair<int,pii> pip;

const int MN = 2e5+5;
const int MOD = 1e9+7;
const int INF = 1e9;

int N,A[MN],X[MN],Y[MN],C[MN],L[MN],R[MN],T[MN];
vector<int> V[MN];

void upt(int s, int e, int x, int v, int i)
{
	int m = (s+e)/2;
	if(s==e){
		T[i] = v;
		return;
	}
	if(x<=m) upt(s,m,x,v,i<<1);
	else upt(m+1,e,x,v,i<<1|1);
	T[i] = A[T[i<<1]]>A[T[i<<1|1]] ? T[i<<1] : T[i<<1|1];
}

int getm(int s, int e, int x, int y, int i)
{
	if(e<x||y<s) return 0;
	if(x<=s&&e<=y) return T[i];
	int m = (s+e)/2;
	int l = getm(s,m,x,y,i<<1), r = getm(m+1,e,x,y,i<<1|1);
	return A[l]>A[r] ? l : r;
}

int maxc(int x, int y)
{
	int res = 0;
	for(int i:V[x]){
		if(Y[i]>y) continue;
		res = max(res,C[i]);
	}
	return res;
}

int solve(int s, int e, int y)
{
	if(s<1||e>N||s>e) return 0;
	//cout << s << ' ' << e << ' ' << y << '\n';
	int m = getm(1,N,s,e,1);
	if(L[m]<0) L[m] = solve(s,m-1,A[m]);
	if(R[m]<0) R[m] = solve(m+1,e,A[m]);

	int res = L[m]+R[m]+maxc(m,y);
	res = max(res,solve(s,m-1,y)+R[m]);
	res = max(res,L[m]+solve(m+1,e,y));
	return res;
}

int main()
{
	/*#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
	#endif*/
	
    ios_base::sync_with_stdio(0),cin.tie(0);

    cin >> N;
    for(int i=1; i<=N; i++){
    	cin >> A[i];
    	upt(1,N,i,i,1);
    	L[i] = R[i] = -1;
    }
    A[0] = -1;

    int M,sum = 0;
    cin >> M;
    for(int i=0; i<M; i++){
    	cin >> X[i] >> Y[i] >> C[i];
    	V[X[i]].push_back(i);
    	sum += C[i];
    }
    //cout << maxc(4,3) << '\n';
    cout << sum-solve(1,N,N);
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Incorrect 5 ms 5120 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Incorrect 5 ms 5120 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Incorrect 5 ms 5120 KB Output isn't correct
3 Halted 0 ms 0 KB -