QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #134605 | #2587. 荣誉称号 | eikki | 70 | 4309ms | 14176kb | C++14 | 2.2kb | 2023-08-04 04:12:43 | 2023-08-04 04:12:45 |
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;
c[j][(rng61() % A + 1) % m] += rng61() % B + 1;
}
}
long long cost(int i, int q) { // node i, change to q mod m
if (mem2[i][q]) return cache2[i][q];
long long sum = 0;
for (int e = 0; e < m; e++) {
sum += ((q - e + m) % m) * c[i][e]; // make sure every addition is long long
}
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;
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--) {
gen();
std::cout << dp(1, 0) << std::endl;
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;
}
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 30
Accepted
time: 2ms
memory: 14176kb
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: 3168ms
memory: 14176kb
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: 4309ms
memory: 14164kb
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:
2423919804 143320912688 3432657117717 49231635128384 492393650042986 4919440171125301 4919843180397902 4921862979028499 4921939511020332 4922954661482348
result:
wrong answer 1st lines differ - expected: '2422031421', found: '2423919804'