oj.uz

답안 #807144

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
807144 2023-08-04T14:07:12 Z GrindMachine 별자리 3 (JOI20_constellation3) C++17
14 / 100
 289 ms 450864 KB 
// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 300 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

ll n,m;
vector<ll> a(N);
vector<array<ll,3>> b(N);
ll dp[N][N][N];

ll go(ll l, ll r, ll k){
    if(l > r) return 0;

    if(l == r){
        ll mxc = 0;
        rep1(i,m){
            auto [x,y,c] = b[i];
            if(x == l and y <= k){
                amax(mxc,c);
            }
        }
        return mxc;
    }

    if(dp[l][r][k] != -1){
        return dp[l][r][k];
    }

    pll mx = {-1,-1};
    for(int i = l; i <= r; ++i){
        pll px = {a[i],i};
        amax(mx,px);
    }
        
    auto [val,ind] = mx;
    
    ll ans = go(l,ind-1,k) + go(ind+1,r,val);
    amax(ans,go(l,ind-1,val) + go(ind+1,r,k));

    ll best = 0;
    rep1(i,m){
        auto [x,y,c] = b[i];
        if(x == ind and y <= k){
            amax(best,c);
        }
    }

    amax(ans, best + go(l,ind-1,val) + go(ind+1,r,val));

    return dp[l][r][k] = ans;
}

void solve(int test_case)
{
    cin >> n;
    rep1(i,n) cin >> a[i];
    cin >> m;
    rep1(i,m) rep(j,3) cin >> b[i][j];

    ll sum = 0;
    rep1(i,m) sum += b[i][2];

    memset(dp,-1,sizeof dp);
    ll ans = sum-go(1,n,n);
    cout << ans << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 222480 KB Output is correct
2 Correct 74 ms 222416 KB Output is correct
3 Correct 72 ms 222368 KB Output is correct
4 Correct 71 ms 222412 KB Output is correct
5 Correct 72 ms 222408 KB Output is correct
6 Correct 74 ms 222392 KB Output is correct
7 Correct 72 ms 222324 KB Output is correct
8 Correct 73 ms 222400 KB Output is correct
9 Correct 72 ms 222328 KB Output is correct
10 Correct 88 ms 222412 KB Output is correct
11 Correct 81 ms 222328 KB Output is correct
12 Correct 80 ms 222328 KB Output is correct
13 Correct 78 ms 222368 KB Output is correct
14 Correct 74 ms 222412 KB Output is correct
15 Correct 75 ms 222336 KB Output is correct
16 Correct 93 ms 222436 KB Output is correct
17 Correct 73 ms 222372 KB Output is correct
18 Correct 80 ms 222424 KB Output is correct
19 Correct 77 ms 222348 KB Output is correct
20 Correct 73 ms 222360 KB Output is correct
21 Correct 80 ms 222316 KB Output is correct
22 Correct 73 ms 222416 KB Output is correct

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 222480 KB Output is correct
2 Correct 74 ms 222416 KB Output is correct
3 Correct 72 ms 222368 KB Output is correct
4 Correct 71 ms 222412 KB Output is correct
5 Correct 72 ms 222408 KB Output is correct
6 Correct 74 ms 222392 KB Output is correct
7 Correct 72 ms 222324 KB Output is correct
8 Correct 73 ms 222400 KB Output is correct
9 Correct 72 ms 222328 KB Output is correct
10 Correct 88 ms 222412 KB Output is correct
11 Correct 81 ms 222328 KB Output is correct
12 Correct 80 ms 222328 KB Output is correct
13 Correct 78 ms 222368 KB Output is correct
14 Correct 74 ms 222412 KB Output is correct
15 Correct 75 ms 222336 KB Output is correct
16 Correct 93 ms 222436 KB Output is correct
17 Correct 73 ms 222372 KB Output is correct
18 Correct 80 ms 222424 KB Output is correct
19 Correct 77 ms 222348 KB Output is correct
20 Correct 73 ms 222360 KB Output is correct
21 Correct 80 ms 222316 KB Output is correct
22 Correct 73 ms 222416 KB Output is correct
23 Runtime error 289 ms 450864 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 222480 KB Output is correct
2 Correct 74 ms 222416 KB Output is correct
3 Correct 72 ms 222368 KB Output is correct
4 Correct 71 ms 222412 KB Output is correct
5 Correct 72 ms 222408 KB Output is correct
6 Correct 74 ms 222392 KB Output is correct
7 Correct 72 ms 222324 KB Output is correct
8 Correct 73 ms 222400 KB Output is correct
9 Correct 72 ms 222328 KB Output is correct
10 Correct 88 ms 222412 KB Output is correct
11 Correct 81 ms 222328 KB Output is correct
12 Correct 80 ms 222328 KB Output is correct
13 Correct 78 ms 222368 KB Output is correct
14 Correct 74 ms 222412 KB Output is correct
15 Correct 75 ms 222336 KB Output is correct
16 Correct 93 ms 222436 KB Output is correct
17 Correct 73 ms 222372 KB Output is correct
18 Correct 80 ms 222424 KB Output is correct
19 Correct 77 ms 222348 KB Output is correct
20 Correct 73 ms 222360 KB Output is correct
21 Correct 80 ms 222316 KB Output is correct
22 Correct 73 ms 222416 KB Output is correct
23 Runtime error 289 ms 450864 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -