QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#507680#8276. Code CongestionniolleTL 0ms0kbC++201.9kb2024-08-06 20:10:542024-08-06 20:10:58

Judging History

你现在查看的是最新测评结果

  • [2024-08-06 20:10:58]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-08-06 20:10:54]
  • 提交

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

output:


result: