Submission #65465298

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
bool dp_greater(const int &a, const int &b, const vector<int> &dp) {
    return dp[a] > dp[b];
}
bool dp_less(const int &a, const int &b, const vector<int> &dp) {
    return dp[a] < dp[b];
}
bool gain_plus_used_less(int a, int b, const vector<int> &g, const vector<char> &u) {
    return g[a] + u[a] < g[b] + u[b];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    vector<int> C(N), A(N), dp(N, 1e9), ord(N);
    vector<vector<int>> prev(N);
    for(int i = 1; i < N; i++) cin >> C[i];
    for(int i = 1; i < N; i++) cin >> A[i];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include<bits/stdc++.h>
using namespace std;

bool dp_greater(const int &a, const int &b, const vector<int> &dp) {
    return dp[a] > dp[b];
}
bool dp_less(const int &a, const int &b, const vector<int> &dp) {
    return dp[a] < dp[b];
}
bool gain_plus_used_less(int a, int b, const vector<int> &g, const vector<char> &u) {
    return g[a] + u[a] < g[b] + u[b];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    vector<int> C(N), A(N), dp(N, 1e9), ord(N);
    vector<vector<int>> prev(N);
    for(int i = 1; i < N; i++) cin >> C[i];
    for(int i = 1; i < N; i++) cin >> A[i];
    dp[0] = 0;
    for(int i = 1; i < N; i++) {
        for(int j = max(0, i - C[i]); j < i; j++)
            dp[i] = min(dp[i], dp[j] + 1);
        for(int j = max(0, i - C[i]); j < i; j++)
            if(dp[j] + 1 == dp[i]) prev[i].push_back(j);
    }
    vector<char> used(N);
    vector<int> target;
    iota(ord.begin(), ord.end(), 0);
    for(int i = 1; i < N; i++) if(A[i]) target.push_back(i);

    sort(target.begin(), target.end(),
         [&](int a, int b){ return dp_greater(a, b, dp); });
    sort(ord.begin(), ord.end(),
         [&](int a, int b){ return dp_less(a, b, dp); });

    for(int t : target) {
        vector<int> g(N, -1e9); g[0] = 0;
        for(int v : ord) if(v)
            for(int u : prev[v])
                g[v] = max(g[v], g[u] + used[u]);

        for(int v = t; v && !used[v]; ) {
            used[v] = 1;
            v = *max_element(prev[v].begin(), prev[v].end(),
                [&](int a, int b){ return gain_plus_used_less(a, b, g, used); });
        }
    }
    cout << accumulate(used.begin(), used.end(), 0) << "\n";
}

Submission Info

Judge Result