QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#284049 | #7877. Balanced Array | SpaceJellyfish | WA | 1ms | 3400kb | C++17 | 986b | 2023-12-15 21:48:52 | 2023-12-15 21:48:52 |
Judging History
answer
#include <iostream>
#include <cstring>
using namespace std;
const int N = 501, p = 998244353;
void addmod(int &x, int y) {
x += y;
if(x >= p)
x -= p;
}
int n, m, a[N], nxt[N];
int dp[2][N][2], (*f)[2] = dp[0], (*g)[2] = dp[1];
const int SZ = sizeof(int) * N * 2;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
int p = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
m += a[i];
while(p < m)
nxt[p++] = m;
}
g[0][0] = 1;
for (int i = 0; i < m; i++) {
swap(f, g);
memset(g, 0, SZ);
for (int j = i; j <= m; j++) {
addmod(g[j][0], f[j][0]);
for (int k = 0; k <= 1; k++) {
if(j < m)
addmod(g[j + 1][0], f[j][k]);
if(nxt[j] > j)
addmod(f[nxt[j]][1], f[j][k]);
}
}
}
cout << g[m][0];
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3400kb
input:
3 1 2 3
output:
34
result:
wrong answer 1st lines differ - expected: '001', found: '34'