QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #746437 | #2587. 荣誉称号 | propane | 100 ✓ | 2663ms | 130460kb | C++20 | 2.4kb | 2024-11-14 14:38:43 | 2024-11-14 14:38:44 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
using LL = long long;
const int maxn = 1e7 + 5;
int n, k, m;
int a[maxn], b[maxn];
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(){
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 dep[maxn];
LL sum[1 << 11][200];
LL dp[1 << 12][200], tmp[200];
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
int T;
cin >> T;
while(T--){
gen();
if (n < (1 << (k + 1))){
for(int i = n + 1; i < (1 << (k + 1)); i++){
a[i] = b[i] = 0;
}
n = (1 << (k + 1)) - 1;
}
for(int i = 1; i < 1 << (k + 1); i++){
memset(sum[i], 0, sizeof sum[i]);
}
dep[1] = 0;
for(int i = 2; i <= n; i++) dep[i] = dep[i / 2] + 1;
for(int i = n; i >= 1; i--){
int t = i >> (dep[i] - dep[i] % (k + 1));
sum[t][a[i] % m] += b[i];
}
for(int i = (1 << (k + 2)) - 1; i >= (1 << (k + 1)); i--){
memset(dp[i], 0x3f, sizeof dp[i]);
dp[i][0] = 0;
}
for(int i = (1 << (k + 1)) - 1; i >= 1; i--){
memset(dp[i], 0, sizeof dp[i]);
if (i > n){
memset(dp[i], 0x3f, sizeof dp[i]);
dp[i][0] = 0;
}
else{
memset(dp[i], 0x3f, sizeof dp[i]);
memset(tmp, 0, sizeof tmp);
for(int a = 0; a < m; a++){
for(int b = 0; b < m; b++){
int cost = a - b;
if (cost < 0) cost += m;
tmp[a] += cost * sum[i][b];
}
}
for(int a = 0; a < m; a++){
for(int b = 0; b < m; b++){
int t = (a - b + m) % m;
dp[i][a] = min(dp[i][a], tmp[b] + dp[2 * i][t] + dp[2 * i + 1][t]);
}
}
}
}
cout << dp[1][0] << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 30
Accepted
time: 0ms
memory: 18632kb
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: 1803ms
memory: 19532kb
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: 2663ms
memory: 130460kb
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