QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#563303 | #7875. Queue Sorting | BreakPlus | WA | 21ms | 7144kb | C++14 | 1.5kb | 2024-09-14 09:35:18 | 2024-09-14 09:35:19 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define pb emplace_back
#define fi first
#define se second
#define mkp make_pair
const ll mod = 998244353;
inline ll read() { ll x; scanf("%lld",&x); return x; }
inline ll lg2(ll x){ return 63^__builtin_clzll(x); }
inline ll qpow(ll a,ll b){
ll ans=1, base=a;
while(b){
if(b&1) ans=ans*base%mod;
base=base*base%mod; b>>=1;
}
return ans;
}
ll n,a[505],f[505][505];
void init(){ }
inline void addmod(ll &a, ll b){
a += b; if(a >= mod) a -= mod;
}
inline void Addmod(ll &a, ll b){
a = (a + b) % mod;
}
ll C[505][505];
void procedure(){
n=read();
C[0][0]=1;
for(ll i=1;i<=n;i++){
C[i][0]=1;
for(ll j=1;j<=i;j++){
C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
}
for(ll i=1;i<=n;i++) a[i]=read();
f[0][0]=1;
for(ll i=0;i<n;i++){
for(ll j=0;j<=n;j++){
if(!f[i][j]) continue;
// cout<<"here "<<i<<", "<<j<<" has "<<f[i][j]<<endl;
addmod(f[i+1][j+a[i+1]], f[i][j]);
// cout<<"trans to "<<i+1<<" "<<j+a[i]<<endl;
for(ll k=0;k<j;k++){
for(ll l=0;l<a[i+1];l++){
if(l) Addmod(f[i+1][j-k+l], f[i][j] * C[l-1+j-k][j-k]);
else addmod(f[i+1][j-k+l], f[i][j]);
}
}
}
}
ll ans=0;
for(ll i=0;i<=n;i++) addmod(ans, f[n][i]);
printf("%lld\n", ans);
}
int main(){
#ifdef LOCAL
assert(freopen("input.txt","r",stdin));
assert(freopen("output.txt","w",stdout));
#endif
ll T=1; init();
// T=read();
while(T--) procedure();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5964kb
input:
4 1 1 1 1
output:
14
result:
ok 1 number(s): "14"
Test #2:
score: -100
Wrong Answer
time: 21ms
memory: 7144kb
input:
300 0 5 2 2 1 0 3 2 2 5 2 1 1 2 1 3 2 3 2 0 0 0 0 1 2 2 3 0 2 2 3 2 0 2 3 0 6 0 0 2 0 1 3 2 1 1 1 3 4 0 1 0 4 1 1 1 1 1 1 2 3 2 1 2 3 2 3 0 5 3 3 2 0 1 1 0 2 1 1 2 0 0 2 1 1 3 2 2 1 2 1 3 0 3 0 1 2 2 0 5 0 2 2 0 0 0 1 2 1 4 2 1 1 0 3 0 2 0 3 1 1 2 0 2 1 1 0 2 0 1 2 2 3 3 1 1 1 1 0 1 3 3 1 0 2 2 4 2 ...
output:
524016798
result:
wrong answer 1st numbers differ - expected: '507010274', found: '524016798'