QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #531182 | #9220. Bus Analysis | ucup-team4504# | WA | 162ms | 10924kb | C++17 | 2.0kb | 2024-08-24 19:04:34 | 2024-08-24 19:04:36 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 105, mod = 1e9 + 7;
int n, t[N], ans;
int f[2][80][80][80], g[2][80][80][80];
//Ç° i ¸öµÄ²éƱ·½°¸Êý£¬Ã¿¸ö·½°¸µÄ×îºó dp ÖµµÄ×ܺÍ
void upd(int &x, int y){
x = (x + y) % mod;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("in.txt", "r", stdin);
// freopen("out2.txt", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++) cin >> t[i];
f[0][75][75][75] = 1;
for (int i = 1; i <= n; i++){
int i1 = i & 1, i2 = i1 ^ 1;
for (int p1 = 1; p1 <= 75; p1++)
for (int p2 = p1; p2 <= 75; p2++)
for (int p3 = p2; p3 <= 75; p3++)
f[i1][p1][p2][p3] = g[i1][p1][p2][p3] = 0;
for (int p1 = 1; p1 <= 75; p1++)
for (int p2 = p1; p2 <= 75; p2++)
for (int p3 = p2; p3 <= 75; p3++)
if (f[i - 1][p1][p2]){
int np1 = min(75, p1 + t[i] - t[i - 1]), np2 = min(75, p2 + t[i] - t[i - 1]), np3 = min(75, p3 + t[i] - t[i - 1]);
upd(f[i1][np1][np2][np3], f[i2][p1][p2][p3]);
upd(g[i1][np1][np2][np3], g[i2][p1][p2][p3]);
}
for (int p1 = 1; p1 <= 75; p1++)
for (int p2 = p1; p2 <= 75; p2++)
for (int p3 = p2; p3 <= 75; p3++)
if (f[i - 1][p1][p2]){
int np1 = min(75, p1 + t[i] - t[i - 1] - 1), np2 = min(75, p2 + t[i] - t[i - 1] - 1), np3 = min(75, p3 + t[i] - t[i - 1] - 1);
bool same = np1 < 20 || np3 < 75;
if (same){
np1 = min(75, np1 + 1);
np2 = min(75, np2 + 1);
np3 = min(75, np3 + 1);
upd(f[i1][np1][np2][np3], f[i2][p1][p2][p3]);
upd(g[i1][np1][np2][np3], g[i2][p1][p2][p3]);
}else{
np3 = min(75, np2 + 1);
np2 = min(75, np1 + 1);
np1 = 1;
upd(f[i1][np1][np2][np3], f[i2][p1][p2][p3]);
upd(g[i1][np1][np2][np3], (g[i2][p1][p2][p3] + f[i2][p1][p2][p3]) % mod);
}
}
}
for (int p1 = 1; p1 <= 75; p1++)
for (int p2 = p1; p2 <= 75; p2++)
for (int p3 = p2; p3 <= 75; p3++)
upd(ans, g[n & 1][p1][p2][p3]);
cout << 2ll * ans % mod;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 10736kb
input:
3 1 8 20
output:
14
result:
ok 1 number(s): "14"
Test #2:
score: 0
Accepted
time: 2ms
memory: 10924kb
input:
5 25 45 65 85 1000000000
output:
156
result:
ok 1 number(s): "156"
Test #3:
score: -100
Wrong Answer
time: 162ms
memory: 10836kb
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:
705747670
result:
wrong answer 1st numbers differ - expected: '932594593', found: '705747670'