oj.uz

답안 #358120

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
358120 2021-01-25T07:04:02 Z ijxjdjd 별자리 3 (JOI20_constellation3) C++14
0 / 100
 46 ms 23788 KB 
#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
using namespace std;

using ll = long long;

const int MAXN = (int)(2e5) + 5;
struct Seg {
    ll mx[4*MAXN];
    Seg() {
        memset(mx, 0, sizeof(mx));
    }
    void upd(int i, ll val, int n = 1, int tl = 0, int tr = MAXN-1) {
        if (tl == tr) {
            if (val == -1) {
                mx[n] = -1;
            }
            else {
                mx[n] = max(mx[n], val);
            }
        }
        else {
            int tm = (tl + tr)/2;
            if (i <= tm) {
                upd(i, val, 2*n, tl, tm);
            }
            else {
                upd(i, val, 2*n+1, tm+1, tr);
            }
            mx[n] = max(mx[2*n], mx[2*n+1]);
        }
    }
    ll get(int l, int r, int n = 1, int tl=0,int tr=MAXN-1) {
        if (l <= tl && tr <= r) {
            return mx[n];
        }
        else if (r < tl || l > tr) {
            return -1;
        }
        else {
            int tm = (tl + tr)/2;
            return max(get(l, r, 2*n, tl, tm), get(l, r, 2*n+1, tm+1, tr));
        }
    }
};
Seg byY;
Seg byX;
Seg heights;
int A[MAXN];
vector<pair<int, ll>> store[MAXN];
int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N;
	cin >> N;
	FR(i, N) cin >> A[i];
	int M;
	cin >> M;
	ll tot = 0;
	FR(i, M) {
	    int a, b, c;
	    cin >> a >> b >> c;
	    	    tot += c;
        a--;
        store[a].push_back({b, c});
	}
	FR(i, MAXN) {
        heights.upd(i, -1);
	}
	ll curMax = 0;
	FR(i, N) {
        curMax = max(curMax, byY.get(0, A[i]));
        for (auto point : store[i]) {
//            cout << heights.get(point.first, N) << endl;
            ll next = max(curMax, byX.get(0, heights.get(point.first, MAXN-1))) + point.second;
            byX.upd(i, next);
            byY.upd(point.first, curMax+point.second);
        }
        heights.upd(A[i], i);
	}
	cout << tot - byX.get(0, MAXN-1) << '\n';
	return 0;
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 65.0

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