oj.uz

답안 #249667

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
249667 2020-07-15T14:11:58 Z egekabas 별자리 3 (JOI20_constellation3) C++14
0 / 100
 4 ms 5120 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
int n, m;
int a[200009];
vector<pii> b[200009];
int dp[200009];
int tot;
int seg[800009];
void build(int v, int tl, int tr){
    if(tl == tr){
        seg[v] = a[tl];
        return;
    }
    build(2*v, tl, (tl+tr)/2);
    build(2*v+1, (tl+tr)/2+1, tr);
    seg[v] = max(seg[2*v], seg[2*v+1]);
}
int get(int v, int tl, int tr, int val){
    if(seg[v] < val) return n;
    if(tl == tr) return tl;
    if(seg[2*v+1] < val)
        return get(2*v, tl, (tl+tr)/2, val);
    return get(2*v+1, (tl+tr)/2+1, tr, val);
}
void erase(int v, int tl, int tr, int idx){
    if(tl == tr){
        seg[v] = -1;
        return;
    }
    if(idx <= (tl+tr)/2)
        erase(2*v, tl, (tl+tr)/2, idx);
    else
        erase(2*v+1, (tl+tr)/2+1, tr, idx);
    seg[v] = max(seg[2*v], seg[2*v+1]);
}
int extra[200009];
int main() {
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    cin >> n;
    for(int i = 0; i < n; ++i)
        cin >> a[i];
    cin >> m;
    while(m--){
        int x, y, c;
        cin >> x >> y >> c;
        b[x-1].pb({y, c});
        tot += c;
    }
    build(1, 0, n-1);
    deque<pii> v = {{1e9+9, n}};
    for(int i = n-1; i >= 0; --i){
        erase(1, 0, n-1, i);
        extra[i] = max(extra[i], extra[i+1]);
        dp[i] = dp[i+1];
        for(auto u : b[i]){
            int bef = get(1, 0, n-1, u.ff);
            if(bef < i)
                extra[bef] = max(extra[bef], extra[i]+u.ss);
            int idx = (*lower_bound(v.begin(), v.end(), mp(u.ff, 0))).ss;
            dp[i] = max(dp[i], u.ss+dp[idx]+extra[i]-extra[idx]);
        }
        while(v[0].ff <= a[i])
            v.pop_front();
        v.push_front({a[i], i});
    }
    cout << tot-dp[0] << '\n';
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 65.0

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