QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#71840	#2587. 荣誉称号	He_Ren	100 ✓	2615ms	88252kb	C++23	2.2kb	2023-01-12 01:30:24	2023-01-12 01:37:44

Judging History

你现在查看的是最新测评结果

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-01-12 01:37:44]
评测

测评结果：100
用时：2615ms
内存：88252kb

查看

[2023-01-12 01:30:24]
提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 1e7 + 5;
const int MAXM = 2e2 + 5;
const int ALL = (1 << 11) + 5;

inline void chk_min(ll &a, ll b) {
    if (a > b)
        a = b;
}

#define bbit(i) (1<<(i))
#define bdig(x,i) (((x)>>(i))&1)

namespace Gen {
unsigned int SA, SB, SC;
int p, A, B;
unsigned int rng61() {
    SA ^= SA << 16;
    SA ^= SA >> 5;
    SA ^= SA << 1;
    unsigned int t = SA;
    SA = SB;
    SB = SC;
    SC ^= t ^ SA;
    return SC;
}
void gen(int &n, int &k, int &m, int a[], int b[]) {
    scanf("%d%d%d%d%u%u%u%d%d", &n, &k, &m, &p, &SA, &SB, &SC, &A, &B);

    for (int i = 1; i <= p; i++)
        scanf("%d%d", &a[i], &b[i]);

    for (int i = p + 1; i <= n; i++) {
        a[i] = rng61() % A + 1;
        b[i] = rng61() % B + 1;
    }
}
};

int n, d, m;
int a[MAXN], b[MAXN];

inline void chg_f(ll f[MAXM]) {
    static ll g[MAXM];
    memset(g, 0, m << 3);

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < i; ++j)
            g[i] += f[j] * (i - j);

        for (int j = i + 1; j < m; ++j)
            g[i] += f[j] * (i + m - j);
    }

    memcpy(f, g, m << 3);
}

ll f[ALL][MAXM], dp[ALL][MAXM];

void solve(void) {
    Gen::gen(n, d, m, a, b);

    int all = (1 << (d + 1)) - 1;

    for (int i = 1; i <= all; ++i)
        memset(f[i], 0, m << 3);

    for (int i = 1; i <= n; ++i) {
        int t = i;

        while (t > all)
            t >>= (d + 1);

        f[t][a[i] % m] += b[i];
    }

    for (int u = all; u >= 1; --u) {
        chg_f(f[u]);

        if (bdig(u, d)) {
            memcpy(dp[u], f[u], m << 3);
            continue;
        }

        if ((u << 1) > n) {
            memset(dp[u], 0, m << 3);
            continue;
        }

        memset(dp[u], 0x3f, m << 3);

        for (int i = 0; i < m; ++i)
            for (int j = 0; j < m; ++j)
                chk_min(dp[u][(i + j) % m], f[u][i] + dp[u << 1][j] + dp[u << 1 | 1][j]);
    }

    printf("%lld\n", dp[1][0]);
}

int main(void) {
    int T;
    scanf("%d", &T);

    while (T--)
        solve();

    return 0;
}

源文件, 语言: C++23

詳細信息

Test #1:

score: 30

Accepted

time: 3ms

memory: 13360kb

input:

10
100 6 2 100 233935 922673 177972 100 100
50 10
22 68
21 75
14 95
33 60
55 83
1 92
82 65
83 88
99 58
49 82
70 42
2 59
37 20
18 85
98 76
11 67
52 28
73 66
28 24
49 98
50 1
86 78
43 38
22 94
3 35
35 96
74 37
74 64
84 5
34 38
19 58
9 11
52 77
28 48
66 47
29 12
8 49
83 50
20 31
79 43
6 53
6 68
99 11
8...

output:

result:

ok 10 lines

Test #2:

score: 40

Accepted

time: 1402ms

memory: 16700kb

input:

10
100000 8 50 100000 247575 819409 776601 100 100
89 32
56 35
20 7
49 32
42 55
32 35
24 93
93 90
54 27
5 38
14 56
29 68
10 88
76 99
93 25
21 89
100 79
48 63
81 38
52 35
96 59
12 79
100 55
16 61
90 78
31 16
27 33
22 81
79 67
74 22
60 14
51 63
60 16
27 17
90 85
94 33
16 86
88 89
40 52
37 5
44 15
35 5...

output:

116425574
2353851315
35516738695
473739227241
4728624650223
47401343950664
47560130284214
47275898551780
47480558629097
47356398623029

result:

ok 10 lines

Test #3:

score: 30

Accepted

time: 2615ms

memory: 88252kb

input:

10
1000000 10 100 100000 955891 404406 316093 100 100
35 87
53 20
85 45
70 69
93 53
52 46
11 58
11 23
62 12
32 18
35 76
39 91
78 34
37 89
40 18
93 80
40 88
4 60
68 40
52 25
68 7
58 88
60 70
25 65
38 16
66 89
8 11
69 99
15 70
69 28
33 6
82 8
64 99
57 37
99 85
55 84
65 59
6 67
7 91
64 72
69 76
68 51
5...

output:

2422031421
143313816604
3433959129294
49250634554363
492655980277329
4923481281511113
4920530936088745
4922522387109597
4922703666684114
4921961703011552

result:

ok 10 lines