QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #594956 | #9220. Bus Analysis | forgotmyhandle | WA | 322ms | 11660kb | C++14 | 1.7kb | 2024-09-28 11:33:42 | 2024-09-28 11:33:42 |
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[i & 1], 0, sizeof dp[i & 1]);
for (int a = 0; a <= 75; a++) {
for (int b = 0; b <= 75; b++) {
for (int c = 0; c <= 75; c++) {
if (!dp[(i - 1) & 1][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[i & 1][f[0]][f[1]][f[2]], dp[(i - 1) & 1][a][b][c]);
int j = 0;
while (f[j] == 0) ++j;
Madd(ans, j * dp[(i - 1) & 1][a][b][c] % P * pw[n - i] % P);
Madd(dp[i & 1][f[j]][f[j + 1]][f[j + 2]], dp[(i - 1) & 1][a][b][c]);
}
}
}
}
cout << (ans << 1) % P << "\n";
return 0;
}
/*
5
25 45 65 85 1000000000
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 11640kb
input:
3 1 8 20
output:
14
result:
ok 1 number(s): "14"
Test #2:
score: 0
Accepted
time: 0ms
memory: 11660kb
input:
5 25 45 65 85 1000000000
output:
156
result:
ok 1 number(s): "156"
Test #3:
score: -100
Wrong Answer
time: 322ms
memory: 11580kb
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'