QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #594861 | #9220. Bus Analysis | forgotmyhandle | WA | 624ms | 11720kb | C++14 | 1.6kb | 2024-09-28 10:48:04 | 2024-09-28 10:48:04 |
Judging History
answer
#include <iostream>
#include <string.h>
#define int long long
using namespace std;
const int P = 1000000007;
inline void Madd(int& x, int y) { (x += y) >= P ? (x -= P) : 0; }
int n;
int dp[2][80][80][80];
int pw[1005];
int x[1005];
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> x[i];
pw[0] = 1;
for (int i = 1; i <= n; i++) pw[i] = pw[i - 1] * 2 % P;
dp[0][0][0][0] = 1;
int ans = 0;
for (int i = 1; i <= n; i++) {
int d = x[i] - x[i - 1];
memset(dp[1], 0, sizeof dp[1]);
for (int a = 0; a <= 75; a++) {
for (int b = 0; b <= 75; b++) {
for (int c = 0; c <= 75; c++) {
if (!dp[0][a][b][c])
continue;
static int f[6];
f[0] = max(0ll, a - d), f[1] = max(0ll, b - d), f[2] = max(0ll, c - d);
for (int i = 0; i < 5; i++) {
f[i + 1] = max(f[i + 1], f[i] + 20);
if (i + 3 < 6)
f[i + 3] = max(f[i + 3], f[i] + 75);
}
for (int i = 1; i < 6; i++) f[i] = max(f[i], f[i - 1]);
Madd(dp[1][f[0]][f[1]][f[2]], dp[0][a][b][c]);
int j = 0;
while (f[j] == 0) ++j;
Madd(ans, j * dp[0][a][b][c] % P * pw[n - i] % P);
Madd(dp[1][f[j]][f[j + 1]][f[j + 2]], dp[0][a][b][c]);
}
}
}
swap(dp[0], dp[1]);
}
cout << (ans << 1) % P << "\n";
return 0;
}
/*
5
25 45 65 85 1000000000
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 5ms
memory: 11720kb
input:
3 1 8 20
output:
14
result:
ok 1 number(s): "14"
Test #2:
score: 0
Accepted
time: 0ms
memory: 11588kb
input:
5 25 45 65 85 1000000000
output:
156
result:
ok 1 number(s): "156"
Test #3:
score: -100
Wrong Answer
time: 624ms
memory: 11592kb
input:
1000 2 7 9 12 14 17 18 21 22 28 29 33 34 35 37 38 44 45 46 50 58 59 63 66 71 72 75 76 77 78 80 81 83 84 87 92 100 101 107 108 109 112 114 116 118 123 124 131 142 143 144 145 148 150 151 152 153 155 157 158 165 167 168 169 171 176 182 185 190 192 198 202 204 205 212 213 223 224 225 226 229 231 240 24...
output:
250566677
result:
wrong answer 1st numbers differ - expected: '932594593', found: '250566677'