QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #260207 | #1191. Reordering the Documents | lemonilemon# | WA | 0ms | 3728kb | C++20 | 1.5kb | 2023-11-21 22:12:55 | 2023-11-21 22:12:57 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#ifdef genshin
#include <experimental/iterator>
#endif
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using uint = unsigned int;
const double EPS = 1e-8;
const int INF = 0x3F3F3F3F;
const ll LINF = 46 * ll(1e17);
const int MOD = 1e9 + 7;
const int maxn = 1e5 + 25;
int dp[5050], s[5050];
signed main() { ios::sync_with_stdio(0); cin.tie(0);
int n, m;
cin >> n >> m;
dp[0] = 1;
int l = 1, mn = n+1, mx = 0;
for (int i=1;i<=n;++i){
cin >> s[i];
mn = min(mn, s[i]);
mx = max(mx, s[i]);
if (mn == l && mx == i){
int fs = s[l], ss = -1, cnt = 1;
for (int j=l+1;j<=i;++j){
if (s[j] == fs + 1) ++fs, ++cnt;
else if (s[j] == ss + 1 || ss == -1) ss = s[j];
else{
cout << "0\n";
return 0;
}
}
int tr1 = cnt, tr2 = i - l + 1 - cnt;
if (tr1 > tr2) swap(tr1, tr2);
for (int j=n;j>=tr2;--j){
dp[j] = (dp[j - tr1] + dp[j - tr2]) % MOD;
}
for (int j=tr2-1;j>=tr1;--j){
dp[j] = dp[j - tr1];
}
for (int j=tr1-1;j>=0;--j){
dp[j] = 0;
}
l = i+1;
mn = n+1;
mx = 0;
}
}
int ans = 0;
for (int i = n-m;i<=m;++i) ans = (ans + dp[i]) % MOD;
cout << ans << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3680kb
input:
6 3 1 3 4 2 6 5
output:
4
result:
ok answer is '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
6 6 1 3 4 2 6 5
output:
8
result:
ok answer is '8'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
4 4 4 3 1 2
output:
0
result:
ok answer is '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
6 3 1 3 4 2 6 5
output:
4
result:
ok answer is '4'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
6 6 1 3 4 2 6 5
output:
8
result:
ok answer is '8'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
4 4 4 3 1 2
output:
0
result:
ok answer is '0'
Test #7:
score: -100
Wrong Answer
time: 0ms
memory: 3680kb
input:
1000 500 4 5 6 8 10 11 12 13 14 15 20 23 25 26 28 29 33 35 1 2 36 38 3 7 41 9 16 44 48 17 18 51 52 53 19 21 54 22 24 59 61 62 27 67 30 31 32 34 68 69 37 39 73 40 76 77 42 81 83 43 85 45 87 46 89 94 47 95 49 50 97 101 55 103 105 56 57 58 106 60 108 110 63 111 114 64 115 65 119 66 70 71 120 121 72 124...
output:
0
result:
wrong answer expected '11363968', found '0'