QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #648061 | #9220. Bus Analysis | BINYU | WA | 470ms | 9448kb | C++14 | 1.0kb | 2024-10-17 16:51:34 | 2024-10-17 16:51:35 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1000;
const ll mod = 1e9 + 7;
int n,a[N + 5];
ll dp[2][75][75][75],ans,f[N + 5] = {1};
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;i++)
scanf("%d",&a[i]),f[i] = f[i - 1] * 2 % mod;
dp[0][0][0][0] = 2;
for(int i = 1;i <= n;i++)
{
int o = i & 1;
for(int j0 = 0;j0 <= 70;j0++)
for(int j1 = j0;j1 <= 70;j1++)
for(int j2 = j1;j2 <= 70;j2++)
dp[o][j0][j1][j2] = 0;
for(int j0 = 0;j0 <= 70;j0++)
for(int j1 = j0;j1 <= 70;j1++)
for(int j2 = j1;j2 <= 70;j2++)
{
int nj0 = max(0,j0 - (a[i] - a[i - 1]));
int nj1 = max(nj0 + 20,j1 - (a[i] - a[i - 1]));
int nj2 = max(nj1 + 20,j2 - (a[i] - a[i - 1]));
int nj3 = max(nj0 + 70,nj2 + 20);
(dp[o][nj0][nj1][nj2] += dp[o ^ 1][j0][j1][j2]) %= mod;
if(!nj0)
(dp[o][nj1][nj2][nj3] += dp[o ^ 1][j0][j1][j2]) %= mod,
(ans += dp[o ^ 1][j0][j1][j2] * f[n - i]) %= mod;
else (dp[o][nj0][nj1][nj2] += dp[o ^ 1][j0][j1][j2]) %= mod;
}
}
cout<<ans<<"\n";
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 9448kb
input:
3 1 8 20
output:
14
result:
ok 1 number(s): "14"
Test #2:
score: 0
Accepted
time: 2ms
memory: 9432kb
input:
5 25 45 65 85 1000000000
output:
156
result:
ok 1 number(s): "156"
Test #3:
score: -100
Wrong Answer
time: 470ms
memory: 8044kb
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:
567111684
result:
wrong answer 1st numbers differ - expected: '932594593', found: '567111684'