QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#153526 | #2587. 荣誉称号 | eikki | 70 | 4382ms | 14120kb | C++20 | 2.2kb | 2023-08-30 10:04:18 | 2023-08-30 10:04:18 |
Judging History
answer
#include <iostream>
#include <vector>
#include <climits>
long long c[(1 << 11) + 5][205];
bool mem[(1 << 11) + 5][205];
long long cache[(1 << 11) + 5][205];
bool mem2[(1 << 11) + 5][205];
long long cache2[(1 << 11) + 5][205];
unsigned int SA, SB, SC; long long p, A, B, n, k, m;
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(){
std::cin >> n >> k >> m >> p >> SA >> SB >> SC >> A >> B;
for(int i = 1; i <= p; i++) {
int ai, bi;
std::cin >> ai >> bi;
int j = i;
while (j >= (1 << k + 1)) j >>= k + 1;
c[j][ai % m] += bi;
}
for(int i = p + 1; i <= n; i++){
int j = i;
while (j > (1 << k + 1)) j >>= k + 1;
int ai = rng61() % A + 1;
int bi = rng61() % B + 1;
c[j][ai % m] += bi;
}
}
long long cost(int i, int q) {
if (mem2[i][q]) return cache2[i][q];
long long sum = 0;
for (int e = 0; e < m; e++) {
sum += 1LL * ((q - e + m) % m) * c[i][e];
}
mem2[i][q] = true;
return cache2[i][q] = sum;
}
long long dp(int node, int sum) {
if (mem[node][sum]) return cache[node][sum];
if (node < (1 << k)) {
long long best = LLONG_MAX/32;
for (int i = 0; i < m; i++) {
int new_sum = (sum - i + m) % m;
best = std::min(best, cost(node, i) + dp(2*node, new_sum) + dp(2*node+1, new_sum));
}
mem[node][sum] = true;
return cache[node][sum] = best;
}
mem[node][sum] = true;
return cache[node][sum] = cost(node, sum);
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int T;
std::cin >> T;
while (T--) {
for (int j = 0; j < (1 << 11) + 5; j++) {
for (int k1 = 0; k1 < 205; k1++) {
c[j][k1] = 0;
mem[j][k1] = false;
cache[j][k1] = 0;
mem2[j][k1] = false;
cache2[j][k1] = 0;
}
}
gen();
std::cout << dp(1, 0) << std::endl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 30
Accepted
time: 3ms
memory: 14116kb
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:
315 3056 288071 6712311 6329883 15283205 19870126 15122517 19096622 20474992
result:
ok 10 lines
Test #2:
score: 40
Accepted
time: 3216ms
memory: 14120kb
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: 0
Wrong Answer
time: 4382ms
memory: 14056kb
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 3432974259213 49240144712755 492552634717142 4922427451693857 4919485355201719 4921522151666014 4921671119848501 4920967309180736
result:
wrong answer 3rd lines differ - expected: '3433959129294', found: '3432974259213'