제출 #1369497

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1369497		i_love_spring	Election Campaign (JOI15_election_campaign)	C++20	0 / 100	34 ms	10716 KiB

election_campaign

#include <bits/stdc++.h>

using namespace std;

#define ar array
#define ll long long 
const int inf = 2e9;

void solve() {
    int n;
    cin >> n;
    
    vector<vector<int>> g(n);
    for (int i = 1; i < n;i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    int m;
    cin >> m;

    vector<ar<int, 2>> R[n];
    for (int i = 0; i < m;i++) {
        int l, r, c;
        cin >> l >> r >> c;
        if (l > r)
            swap(l, r);
        R[--r].push_back({--l, c});
    }

    vector<ll> dp(n, 0);
    for (int i = 0; i < n;i++) {
        dp[i] = (i - 1 ? dp[i - 1] : dp[i]);
        for (auto [l, c] : R[i]) {
            if (l - 1 >= 0)
                dp[i] = max(dp[i], dp[l - 1] + c);
            else 
                dp[i] = max(dp[i], 0ll + c);
        }
    }

    cout << dp[n - 1] << "\n";
}

int32_t main() { 

#ifdef Behruz
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif 

    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    solve();

    return 0;
}

• 서브태스크 1: 0 / 10
• 서브태스크 2: 0 / 5
• 서브태스크 3: 0 / 5
• 서브태스크 4: 0 / 30
• 서브태스크 5: 0 / 10
• 서브태스크 6: 0 / 40