oj.uz

답안 #1083626

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1083626 2024-09-03T16:33:53 Z phong 별자리 3 (JOI20_constellation3) C++17
0 / 100
 22 ms 25948 KB 
#include<bits/stdc++.h>

#define ll long long
#define int long long
const int nmax = 2e5 + 5, N = 1e5;
const ll oo = 1e18 + 1, base = 311;
const int lg = 20, M = 10;
const ll mod = 998244353, mod2 = 1e9 + 5277;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;

int n, m;
int rmq[nmax][lg + 1], a[nmax];
map<int, int> dp[nmax], g[nmax];
ll f[nmax];

int calc(int u, int j){
//    if(f[u] < g[u][j]) cout << "?";
    dp[u][j] += f[u] - g[u][j];
    g[u][j] = f[u];
    return dp[u][j];
}
int get(int l, int r){
    int k = __lg(r - l + 1);
    int x = rmq[l][k], y = rmq[r - (1 << k) + 1][k];
    if(a[x] > a[y])return x;
    else return y;
}
int one[nmax];

int get(int u){
    return one[u] ? one[u] = get(one[u]) : u;
}
int lmao(int x, int y){
    ll res = 0;
    while(dp[x].size()){
        pii it = *dp[x].begin();
        if(it.fi <= y){
            res = max(res, calc(x, it.fi));
            dp[x].erase(dp[x].begin());
        }
        else break;
    }
    return res;
}
int solve(int l, int r){
    if(l == r) return l;
    int p = get(l, r);
    if(l < p && p < r){
        int x = solve(l, p - 1);
        int y = solve(p + 1, r);
        int t1 = 0, t2 = 0;
        for(int j = 1; j <= a[p]; ++j){
            t1 = max(t1, dp[x][j]);
            t2 = max(t2, dp[y][j]);
        }
        for(int j = 1; j <= n; ++j){
            if(j <= a[p]){
                dp[p][j] = t1 + t2;
            }
            else {
                dp[p][j] = max({dp[x][j] + t2, dp[y][j] +t1, g[p][j] + t1 +t2});
            }
        }
    }
    else{
        int y;
        if(l < p) y = solve(l, p - 1);
        else y = solve(p + 1, r);
        int t2 = 0;
        for(int j = 1; j <= a[p]; ++j){
            t2 = max(t2, dp[y][j]);
        }
        for(int j = 1; j <= n; ++j){
            if(j <= a[p]){
                dp[p][j] = t2;
            }
            else dp[p][j] = max(dp[y][j], g[p][j] + t2);
        }

    }
    return p;
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i], rmq[i][0] = i;
    for(int j = 1; j <= lg; ++j){
        for(int i = 1; i + (1 << j) - 1 <= n; ++i){
            int x = rmq[i][j - 1], y = rmq[i + (1 << (j - 1))][j - 1];
            if(a[x] > a[y]) rmq[i][j] = x;
            else rmq[i][j] = y;
        }
    }
    cin >> m;
    ll sum = 0;
    for(int i = 1, u, v, w; i <= m; ++i){
        cin >> u >> v >> w;
        g[u][v] = w;
        dp[u][v] = w;
        sum += w;
    }
    int p = get(solve(1, n));
    ll ans = 0;
    for(auto [id,w] : dp[p]) ans = max(ans, w);
    cout << ans;
}
/*
5 4
1 2
2 3
3 4
3 5
1 2 1 3 4


*/

Compilation message

constellation3.cpp:88:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   88 | main(){
      | ^~~~

Subtask #1
0 / 14.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 65.0

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