Star's Blog

1
#include <iostream>
2
#include <queue>
3

4
using namespace std;
5

6
int n, m, k;
7
int a[100010];
8
priority_queue<int> q;
9

10
int main() {
11
    int T;
12
    scanf("%d", &T);
13
    while (T--) {
14
        while (!q.empty()) q.pop();
15
        bool fail = false;
16
        scanf("%d%d%d", &n, &m, &k);
17
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
18
        for (int i = 1; i <= n; ++i) {
19
            m -= a[i];
20
            q.push(a[i]);
21
            if (m <= 0 && !q.empty() && k) {
22
                k--;
23
                m += q.top();
24
                q.pop();
25
            }
26
            if (m <= 0) {
27
                fail = true;
28
                printf("%d\n", i - 1);
29
                break;
30
            }
31
        }
32
        if (!fail) printf("%d\n", n);
33
    }
34
    return 0;
35
}

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 1000010;
6

7
int head[N], ne[N * 2], ver[N * 2], w[N * 2], tot;
8
int cnt[N], n;
9
long long res = 0;
10

11
void add(int x, int y, int z) {
12
    ver[++tot] = y;
13
    ne[tot] = head[x];
14
    head[x] = tot;
15
    w[tot] = z;
16
}
17

18
void dp(int x, int fa) {
19
    cnt[x] = 1;
20
    for (int i = head[x]; i; i = ne[i]) {
21
        int y = ver[i];
22
        if (y == fa) continue;
23
        dp(y, x);
24
        cnt[x] += cnt[y];
25
        res += (long long)w[i] * abs(n - cnt[y] * 2);
26
    }
27
}
28

29
int main() {
30
    scanf("%d", &n);
31
    for (int i = 1; i < n; ++i) {
32
        int x, y, z;
33
        scanf("%d%d%d", &x, &y, &z);
34
        add(x, y, z);
35
        add(y, x, z);
36
    }
37
    dp(1, 0);
38
    printf("%lld\n", res);
39
    return 0;
40
}