QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #232891 | #6410. Classical DP Problem | elisaipate | WA | 107ms | 394476kb | C++14 | 1.0kb | 2023-10-31 00:15:24 | 2023-10-31 00:15:26 |
Judging History
answer
#include <iostream>
using namespace std;
#define nmax 5001
#define mod 998244353
int lin[nmax], col[nmax];
long long dp[2][nmax][nmax], n, k;
void fctdp( int ind, int a[] ) {
int i, j;
for( i = 0; i < k; i++ ) {
for( j = 0; j < k+1; j++ ) {
dp[ind][i+1][j] += (long long)(a[i+1] - j) * dp[ind][i][j] % mod;
if( j >= 1 )
dp[ind][i+1][j-1] += (long long)j * dp[ind][i][j] % mod;
}
}
}
int main()
{
int i, j;
long long fact;
cin >> n;
for( i = n; i >= 1; i-- )
cin >> lin[i];
for( i = 1; i <= n; i++) {
for( j = 1; j <= lin[i]; j++ )
col[j]++;
}
k = 1;
while( lin[k] >= k )
k++;
k--;
dp[0][0][lin[k+1]] = 1;
dp[1][0][col[k+1]] = 1;
fctdp( 0, lin );
fctdp( 1, col );
fact = 1;
for( i = 2; i <= k; i++ )
fact = (long long) fact * i % mod;
cout << k << " " << (dp[0][k][0] + dp[1][k][0] - fact) % mod;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5724kb
input:
3 1 2 3
output:
2 6
result:
ok 2 number(s): "2 6"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5664kb
input:
1 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5748kb
input:
2 1 1
output:
1 2
result:
ok 2 number(s): "1 2"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5668kb
input:
2 2 2
output:
2 6
result:
ok 2 number(s): "2 6"
Test #5:
score: 0
Accepted
time: 1ms
memory: 5584kb
input:
3 1 1 1
output:
1 3
result:
ok 2 number(s): "1 3"
Test #6:
score: 0
Accepted
time: 1ms
memory: 5628kb
input:
3 2 2 2
output:
2 9
result:
ok 2 number(s): "2 9"
Test #7:
score: 0
Accepted
time: 1ms
memory: 5632kb
input:
3 3 3 3
output:
3 48
result:
ok 2 number(s): "3 48"
Test #8:
score: 0
Accepted
time: 1ms
memory: 5664kb
input:
5 1 1 3 3 4
output:
3 47
result:
ok 2 number(s): "3 47"
Test #9:
score: 0
Accepted
time: 1ms
memory: 7736kb
input:
10 2 4 5 5 5 5 6 8 8 10
output:
5 864
result:
ok 2 number(s): "5 864"
Test #10:
score: 0
Accepted
time: 1ms
memory: 5668kb
input:
30 6 8 9 9 9 10 13 14 15 15 16 17 17 18 20 22 22 23 23 24 24 25 25 25 27 28 28 29 29 30
output:
17 986189864
result:
ok 2 number(s): "17 986189864"
Test #11:
score: 0
Accepted
time: 1ms
memory: 6000kb
input:
123 1 1 1 2 2 3 3 6 6 7 7 7 8 8 9 9 10 10 10 11 12 12 12 13 14 14 14 14 16 17 17 17 17 17 18 19 20 20 21 21 22 22 22 23 23 23 25 25 26 27 27 28 28 28 28 29 29 30 31 31 31 32 33 33 33 34 35 35 35 36 37 37 38 39 39 39 39 40 41 41 42 42 42 43 44 48 48 50 52 53 55 56 57 57 57 58 65 68 71 74 75 76 76 82 ...
output:
42 287179924
result:
ok 2 number(s): "42 287179924"
Test #12:
score: 0
Accepted
time: 2ms
memory: 8336kb
input:
1234 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 4 5 5 5 5 6 6 7 7 7 7 7 7 7 8 8 8 8 9 9 10 10 10 11 11 11 11 11 12 13 13 14 14 15 15 15 15 16 16 16 17 17 17 18 18 18 19 19 19 19 19 19 19 19 19 19 20 20 20 21 21 21 21 21 22 22 22 23 23 23 23 23 23 23 23 23 24 24 24 24 24 24 24 24 24 24 25 25 25 25 25 26 26 26 26 ...
output:
239 98119841
result:
ok 2 number(s): "239 98119841"
Test #13:
score: 0
Accepted
time: 8ms
memory: 39048kb
input:
2345 1 1 2 2 2 7 7 9 9 9 9 15 17 19 19 22 23 24 25 29 29 29 30 31 32 33 35 37 39 41 42 42 43 43 44 46 46 46 47 48 48 50 51 51 52 53 53 54 55 56 57 58 58 60 61 63 63 64 65 65 65 66 67 67 67 69 69 69 70 71 72 72 73 73 74 75 75 77 77 79 83 85 86 88 90 90 91 93 94 97 99 104 106 107 108 108 109 109 110 1...
output:
1239 588926916
result:
ok 2 number(s): "1239 588926916"
Test #14:
score: 0
Accepted
time: 24ms
memory: 101588kb
input:
3456 4 7 8 8 9 19 20 21 22 23 23 27 29 29 32 32 33 43 45 50 52 52 55 58 58 58 60 62 66 67 68 69 71 74 74 76 77 79 82 82 87 87 88 91 93 95 96 97 99 102 104 106 107 108 121 121 123 126 127 131 137 138 139 142 145 147 152 156 157 159 161 165 166 170 170 172 174 175 178 182 183 185 186 189 190 195 195 1...
output:
2239 24387925
result:
ok 2 number(s): "2239 24387925"
Test #15:
score: 0
Accepted
time: 52ms
memory: 195488kb
input:
4456 4 7 10 10 22 24 29 33 33 34 35 37 40 41 47 48 55 61 61 65 69 71 76 91 95 99 105 105 105 110 112 113 117 117 120 121 122 123 125 127 130 134 135 138 140 141 142 142 144 150 153 154 157 162 165 169 170 170 174 175 176 178 197 198 198 201 208 211 211 212 214 214 215 217 220 224 224 225 230 231 232...
output:
3239 904395650
result:
ok 2 number(s): "3239 904395650"
Test #16:
score: 0
Accepted
time: 84ms
memory: 319400kb
input:
5000 1 5 7 8 24 28 36 47 50 56 59 64 66 85 89 94 95 95 98 108 110 117 122 155 157 158 163 172 172 179 186 197 198 220 236 251 254 254 256 265 287 288 298 302 306 312 327 336 343 344 345 348 350 360 363 364 382 382 390 399 402 406 412 421 425 435 442 445 450 451 453 478 481 490 491 496 499 500 500 50...
output:
4239 328488156
result:
ok 2 number(s): "4239 328488156"
Test #17:
score: -100
Wrong Answer
time: 107ms
memory: 394476kb
input:
5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 ...
output:
5000 -680689503
result:
wrong answer 2nd numbers differ - expected: '317554850', found: '-680689503'