QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#121688 | #6407. Classical A+B Problem | SolitaryDream# | RE | 0ms | 0kb | C++20 | 2.1kb | 2023-07-08 17:59:25 | 2023-07-08 17:59:28 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
#define DOR(i,s,t) for(int i=(s),_t=(t); i>=_t; --i)
typedef long long ll;
const int N=105;
const int Mod=998244353;
int a[N];
ll f[N][N*N];
void solve() {
int n,m,v;
cin >> n >> m >> v;
ll res=0;
FOR(i,1,n) cin >> a[i];
sort(a+1,a+n+1);
int p=n;
f[0][0]=1;
DOR(i,n,1) {
while(a[p]>a[i]+m) {
FOR(j,0,n) FOR(k,0,j*101) {
f[j][k]=f[j][k+101-a[p]];
f[j+1][k+m]=(f[j+1][k+m]-f[j][k])%Mod;
f[j][k+101-a[p]]=(f[j][k+101-a[p]]-f[j][k])%Mod;
}
DOR(j,n,0) FOR(k,0,j*101) {
f[j+1][k+m]=(f[j+1][k+m]+f[j][k])%Mod;
f[j][k]=0;
}
--p;
}
FOR(j,0,v-1) FOR(k,0,j*101) {
if(k+m*i+(n-i-j)*(a[i]+m-101)>=m*v) {
res=(res+f[j][k])%Mod;
}
}
DOR(j,n,0) FOR(k,0,j*101) {
f[j+1][k+m]=(f[j+1][k+m]+f[j][k])%Mod;
f[j][k+101-a[i]]=(f[j][k+101-a[i]]+f[j][k])%Mod;
f[j][k]=0;
}
}
FOR(i,1,n) a[i]=100-a[i];
p=n;
DOR(i,n,1) {
while(a[p]>a[i]+m) {
FOR(j,0,n) FOR(k,0,j*101) {
f[j][k]=f[j][k+101-a[p]];
f[j+1][k+m]=(f[j+1][k+m]-f[j][k])%Mod;
f[j][k+101-a[p]]=(f[j][k+101-a[p]]-f[j][k])%Mod;
}
DOR(j,n,0) FOR(k,0,j*101) {
f[j+1][k+m]=(f[j+1][k+m]+f[j][k])%Mod;
f[j][k]=0;
}
--p;
}
FOR(j,0,n-v-2) FOR(k,0,j*101) {
if(k+m*i+(n-i-j)*(a[i]+m-101)>=m*v) {
res=(res+f[j][k])%Mod;
}
}
DOR(j,n,0) FOR(k,0,j*101) {
f[j+1][k+m]=(f[j+1][k+m]+f[j][k])%Mod;
f[j][k+101-a[i]]=(f[j][k+101-a[i]]+f[j][k])%Mod;
f[j][k]=0;
}
}
cout << res << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while(T--) solve();
return 0;
}
詳細信息
Test #1:
score: 0
Runtime Error
input:
6 2 786 1332 89110 2333333 10000000000000000000000000001