Submission #946898

#	Time	Username	Problem	Language	Result	Execution time	Memory
946898		vjudge1	Constellation 3 (JOI20_constellation3)	C++17	14 / 100	1556 ms	29276 KiB

constellation3

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

struct Sp{
    vector <vector<int>> T;
    int _s;
    Sp(auto &a, int s){
        _s = s;
        T.resize(20);
        int n = a.size();
        for ( auto &x: T ){
            x.resize(n);
        }
        T[0] = a;
        for ( auto &u: T[0] ) u *= _s;
        for ( int i = 1; i < 20; i++ ){
            int k = 1 << i - 1;
            for ( int j = 0; j < n; j++ ){
                T[i][j] = min(T[i - 1][j], T[i - 1][min(n - 1, j + k)]);
            }
        }
    }
    int get(int l, int r){
        int lg = __lg(r - l + 1), k = 1 << lg;
        return min(T[lg][l], T[lg][r - k + 1]) * _s;
    }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    vector <int> a(n);
    for ( auto &u: a ) cin >> u;
    int m; cin >> m;
    vector <int> X(m), Y(m), C(m);
    vector <vector<int>> G(n);
    for ( int i = 0; i < m; i++ ){
        cin >> X[i] >> Y[i] >> C[i];
        --X[i];
        G[X[i]].pb(i);
    }
    vector <int> L(m), R(m);
    Sp sp(a, -1);
    for ( int i = 0; i < n; i++ ){
        for ( auto &j: G[i] ){
            int l = 0, r = n;
            L[j] = R[j] = i;
            while ( l < L[j] ){
                int md = (l + L[j]) / 2;
                if ( sp.get(md, L[j]) >= Y[j] ){
                    l = md + 1;
                } else L[j] = md;
            }
            while ( R[j] + 1 < r ){
                int md = (R[j] + r) / 2;
                if ( sp.get(R[j], md) >= Y[j] ){
                    r = md;
                } else R[j] = md;
            }
            R[j]++, L[j]++, X[j]++;
        }
    }
    vector <int> pos(m);
    iota(all(pos), 0);
    sort(all(pos), [&](int &u, int &v){
         return Y[u] < Y[v];
    });
    vector <vector<int>> dp(n + 2, vector <int> (n + 1)), t(n + 1);
    for ( int i = 0; i < m; i++ ){
        t[X[i]].pb(i);
    }
    for ( int l = n; l > 0; l-- ){
        for ( int r = l; r <= n; r++ ){
            chmax(dp[l][r], max(dp[l + 1][r], dp[l][r - 1]));
            for ( int k = l; k <= r; k++ ){
                for ( auto &i: t[k] ){
                    if ( L[i] < l || R[i] > r ){
                        continue;
                    }
                    chmax(dp[l][r], dp[l][k - 1] + dp[k + 1][r] + C[i]);
                }
            }
        }
    }
    cout << accumulate(all(C), 0LL) - dp[1][n];

    cout << '\n';
}

Compilation message (stderr)

constellation3.cpp:34:8: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   34 |     Sp(auto &a, int s){
      |        ^~~~
constellation3.cpp: In instantiation of 'Sp::Sp(auto:23&, long long int) [with auto:23 = std::vector<long long int>]':
constellation3.cpp:72:16:   required from here
constellation3.cpp:44:28: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   44 |             int k = 1 << i - 1;
      |                          ~~^~~

• Subtask 1: 14 / 14
• Subtask 2: 0 / 21
• Subtask 3: 0 / 65