QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#507680 | #8276. Code Congestion | niolle | TL | 0ms | 0kb | C++20 | 1.9kb | 2024-08-06 20:10:54 | 2024-08-06 20:10:58 |
answer
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dwn(i,a,b) for(int i=a;i>=b;i--)
#define lowbit(x) (x&(-x))
#define MAXN 302501
using namespace std;
typedef long long ll;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch>'9' || ch<'0'){if(ch=='-') f=-1; ch=getchar();}
while('0'<=ch && ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
return x*f;
}
const int mod=998244353;
int n,m,cc,a[MAXN],t[MAXN],sa[MAXN],st[MAXN],mul[MAXN];
int f[2][MAXN],g[2][MAXN],ans;
int ksm(int x,int y){
int res=1;
while(y){
if(y&1) res=res*x%mod;
x=x*x%mod;
y>>=1;
}
return res;
}
void Add(int &x,int y){
x += y;
if(x >= mod) x -= mod;
if(x < 0) x += mod;
}
void pre(){
mul[0] = 1;
rep(i,1,205) mul[i] = mul[i-1] * 2 % mod;
}
int main(){
pre();
cc = read(); n = read(); m = read();
rep(i,1,n) a[i] = read(), sa[i] = sa[i-1] + a[i];
rep(i,1,n) t[i] = read(), st[i] = st[i-1] + t[i];
if(st[n] <= m){
printf("%lld",1ll * mul[n] * sa[n] % mod);
return 0;
}
f[1][0] = 1;
int x = 0, y = 1;
dwn(i,n,1){
swap(x,y);
if(st[i-1] <= m){
rep(j,max(m-st[i]+1,0),m-st[i-1]){
if(f[x][j]) Add(ans, (1ll * (mul[i-1] + mod) * f[x][j] % mod * sa[i-1] + 1ll * g[x][j] * (mul[i-1] + mod)) % mod);
}
}
rep(j,0,m){
f[y][j] = f[x][j];
g[y][j] = g[x][j];
if(j >= t[i] && f[x][j-t[i]]){
Add(f[y][j],f[x][j-t[i]]);
Add(g[y][j],(1ll * f[x][j-t[i]] * a[i] + g[x][j-t[i]]) % mod);
}
}
}
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
f[0][0] = 1;
x = 1; y = 0;
rep(i,1,n){
swap(x,y);
rep(j,m-t[i]+1,m) Add(ans, 1ll * mul[n-i] * g[x][j] % mod);
rep(j,0,m){
f[y][j] = f[x][j];
g[y][j] = g[x][j];
if(j >= t[i] && f[x][j-t[i]]){
Add(f[y][j],f[x][j-t[i]]);
Add(g[y][j],(1ll * f[x][j-t[i]] * a[i] + g[x][j-t[i]]) % mod);
}
}
}
cout << ans;
return 0;
}
详细
Test #1:
score: 0
Time Limit Exceeded
input:
3 3 2 3 4 1 2 2