1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

void solve() {
    int n, m, l;
    cin >> n >> m >> l;
    vi a(n);
    rep(i, 0, n - 1) cin >> a[i];
    vl d(m);
    int l1 = 0, r = 1e9, mid;
    int ans = -1;
    vi tem;
    int res = 0;
    rep(i, 0, n - 1) {
        if (i == 0) {
            if (a[i] == 1)
                continue;
            else
                tem.push_back(a[i]);
            continue;
        }
        tem.push_back(a[i] - a[i - 1]);
    }
    if (a[n - 1] != l) res = l - a[n - 1];
    int m1 = sz(tem);
    auto check = [&](int mid) -> bool {
        fill(all(d), 0LL);
        int maxx = 0;
        rep(i, 0, m1 - 1) {
            int tem2 = m1 - i + 1;
            if (tem2 >= m) {
                sort(all(d));
                ll te = tem[i];
                rep(j, 1, m) {
                    ll diff = (j == m) ? 0 : (d[j] - d[j - 1]);
                    ll cnt = diff * j;
                    if (j < m && te >= cnt) {
                        te -= cnt;
                    } else {
                        ll tem3 = d[j - 1] + te / j;
                        ll re = te % j;
                        rep(v, 0, j - 1) { d[v] = tem3 + (v >= j - re ? 1 : 0); }
                        break;
                    }
                }
                sort(all2(d));
                d[0] = 0;
            } else {
                sort(all2(d));
                sort(d.begin(), d.begin() + tem2);
                ll te = tem[i];
                rep(j, 1, tem2) {
                    ll diff = (j == tem2) ? 0 : (d[j] - d[j - 1]);
                    ll cnt = diff * j;
                    if (j < tem2 && te >= cnt) {
                        te -= cnt;
                    } else {
                        ll tem3 = d[j - 1] + te / j;
                        ll re = te % j;
                        rep(v, 0, j - 1) { d[v] = tem3 + (v >= j - re ? 1 : 0); }
                        break;
                    }
                }
                sort(all2(d));
                d[0] = 0;
            }
        }
        sort(all2(d));
        return d[0] + res <= mid;
    };
    while (l1 <= r) {
        mid = (l1 + r) / 2;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        } else
            l1 = mid + 1;
    }
    cout << ans << endl;
    return;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

void solve() {
    int n;
    ll h;
    cin >> n >> h;
    vl pre(n);
    vl suf(n);
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    rep(i, 0, n - 1) a[i] = h - a[i];
    ll maxx = LLONG_MIN;
    rep(i, 0, n - 1) {
        ll tot = 0;
        ll tem = LLONG_MAX;
        frep(j, i, 0) {
            tem = min(tem, a[j]);
            tot += tem;
        }
        pre[i] = tot;
    }
    frep(i, n - 1, 0) {
        ll tot = 0;
        ll tem = LLONG_MAX;
        rep(j, i, n - 1) {
            tem = min(tem, a[j]);
            tot += tem;
        }
        suf[i] = tot;
    }
    vl cnt(n);
    rep(i, 0, n - 1) {
        cnt[i] = pre[i] + suf[i] - a[i];
        maxx = max(maxx, cnt[i]);
    }
    rep(i, 0, n - 1) {
        int idx = i;
        rep(j, i + 1, n - 1) {
            if (a[j] < a[idx]) idx = j;
            maxx = max(maxx, cnt[i] + cnt[j] - cnt[idx]);
        }
    }
    cout << maxx << endl;
    return;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

void solve() {
    int n, k, v, x, y;
    cin >> n >> k >> v;
    v--;
    vvi ma(n);
    rep(i, 1, n - 1) {
        cin >> x >> y;
        ma[x - 1].push_back(y - 1);
        ma[y - 1].push_back(x - 1);
    }
    vi dis(n, 1);
    auto dfs = [&](this auto&& dfs, int x, int pa) -> void {
        bool isleaf = true;
        dis[x] = INT_MAX / 3;
        for (int& p : ma[x]) {
            if (p == pa) continue;
            isleaf = false;
            dfs(p, x);
            if (dis[x] + dis[p] < k + 3) dis[x] = 1;
            dis[x] = min(dis[x], dis[p] + 1);
        }
        if (isleaf) dis[x] = 1;
    };
    dfs(v, -1);
    if (dis[v] == 1)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

void solve() {
    int n;
    cin >> n;
    vi a(n);
    rep(i, 0, n - 1) cin >> a[i];
    vi b(n);
    vector<bool> vis(n + 1, false);
    rep(i, 0, n - 1) {
        if (a[i] <= n) vis[a[i]] = true;
    }
    bool flag = true;
    rep(i, 0, n - 1) {
        if (i >= 1 && a[i] > a[i - 1]) {
            flag = false;
            break;
        }
        if (a[i] < n - i - 1 || a[i] > n) {
            flag = false;
            break;
        }
    }
    if (!flag) {
        cout << "NO" << endl;
        return;
    }
    cout << "YES" << endl;
    vi tem;
    rep(i, 0, n) {
        if (vis[i])
            continue;
        else
            tem.push_back(i);
    }
    rep(i, 0, n - 1) {
        if (i == 0) {
            b[i] = tem.back();
            tem.pop_back();
            continue;
        }
        if (a[i] == a[i - 1]) {
            b[i] = tem.back();
            tem.pop_back();
        } else {
            b[i] = 1e9;
        }
    }
    rep(i, 0, n - 1) cout << b[i] << ' ';
    cout << endl;
    return;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

const int MOD = 1e9 + 7;
void solve() {
    int n;
    cin >> n;
    vi a(n);
    rep(i, 0, n - 1) cin >> a[i];
    ll ans = 1;
    vi b(n);
    vector<bool> vis(n + 1, false);
    rep(i, 0, n - 1) {
        if (a[i] <= n) vis[a[i]] = true;
    }
    bool flag = true;
    rep(i, 0, n - 1) {
        if (i >= 1 && a[i] > a[i - 1]) {
            flag = false;
            break;
        }
        if (a[i] < n - i - 1 || a[i] > n) {
            flag = false;
            break;
        }
    }
    if (!flag) {
        cout << 0 << endl;
        return;
    }
    vi pre(n + 1);
    rep(i, 0, n) {
        if (vis[i])
            pre[i] = pre[i - 1];
        else
            pre[i] = pre[i - 1] + 1;
    }
    rep(i, 0, n - 1) {
        if (i >= 1 && a[i] == a[i - 1]) {
            ans *= 1LL * (a[i] - (n - i - 1));
            ans %= MOD;
        } else {
            ans *= 1LL * (i + 1);
            ans %= MOD;
        }
    }
    cout << ans << endl;
    return;
}