QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#354128#8276. Code Congestionucup-team134#TL 27ms475184kbC++174.8kb2024-03-14 22:11:072024-03-14 22:11:08

Judging History

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

  • [2024-03-14 22:11:08]
  • 评测
  • 测评结果:TL
  • 用时:27ms
  • 内存:475184kb
  • [2024-03-14 22:11:07]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ll long long
#define pb push_back
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL)
#define ld long double
#define li __int128

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<int D, typename T>struct vec : public vector<vec<D - 1, T>> {template<typename... Args>vec(int n = 0, Args... args) : vector<vec<D - 1, T>>(n, vec<D - 1, T>(args...)) {}};
template<typename T>struct vec<1, T> : public vector<T> {vec(int n = 0, T val = T()) : vector<T>(n, val) {}};
template<class T1,class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const deque<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T,greater<T> >& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T,greater<T> >& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T1,class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
int ri(){int x;scanf("%i",&x);return x;}
void rd(int&x){scanf("%i",&x);}
void rd(long long&x){scanf("%lld",&x);}
void rd(double&x){scanf("%lf",&x);}
void rd(long double&x){scanf("%Lf",&x);}
void rd(string&x){cin>>x;}
void rd(char*x){scanf("%s",x);}
template<typename T1,typename T2>void rd(pair<T1,T2>&x){rd(x.first);rd(x.second);}
template<typename T>void rd(vector<T>&x){for(T&p:x)rd(p);}
template<typename C,typename...T>void rd(C&a,T&...args){rd(a);rd(args...);}
//istream& operator>>(istream& is,__int128& a){string s;is>>s;a=0;int i=0;bool neg=false;if(s[0]=='-')neg=true,i++;for(;i<s.size();i++)a=a*10+s[i]-'0';if(neg)a*=-1;return is;}
//ostream& operator<<(ostream& os,__int128 a){bool neg=false;if(a<0)neg=true,a*=-1;ll high=(a/(__int128)1e18);ll low=(a-(__int128)1e18*high);string res;if(neg)res+='-';if(high>0){res+=to_string(high);string temp=to_string(low);res+=string(18-temp.size(),'0');res+=temp;}else res+=to_string(low);os<<res;return os;}
const int mod=998244353;
int add(int a,int b){
    a+=b;
    if(a>=mod)
        a-=mod;
    return a;
}
int sub(int a,int b){
    a-=b;
    if(a<0)
        a+=mod;
    return a;
}
int mul(int a,int b){
    return (long long)a*b%mod;
}
const int N=201,T=3e5+5;
int ways[N][T],a[N],t[N],tmax;
int ways2[N][T];
int n;
int calc(int i,int tt){
	if(i<0){
		if(tt==0)
		return 1;
		else return 0;
	}
	if(ways[i][tt]!=-1)return ways[i][tt];
	ways[i][tt]=calc(i-1,tt);
	if(t[i]<=tt){
		ways[i][tt]=add(ways[i][tt],calc(i-1,tt-t[i]));
	}
	return ways[i][tt];
}
int calc2(int i,int tt){
	if(i==n){
		if(tt==0)
		return 1;
		else return 0;
	}
	if(ways2[i][tt]!=-1)return ways2[i][tt];
	ways2[i][tt]=calc2(i+1,tt);
	if(t[i]<=tt){
		ways2[i][tt]=add(ways2[i][tt],calc2(i+1,tt-t[i]));
	}
	return ways2[i][tt];
}
int main()
{
	memset(ways,-1,sizeof ways);
	memset(ways2,-1,sizeof ways2);
	n=ri();
	tmax=ri();
	for(int i=0;i<n;i++){
		a[i]=ri();
	}
	for(int i=0;i<n;i++){
		t[i]=ri();
	}
	vector<int> pw(n);
	pw[0]=1;
	for(int i=1;i<n;i++){
		pw[i]=add(pw[i-1],pw[i-1]);
	}
	int ans=0;
	int sm=0;
	for(int i=0;i<n;i++){
		// Counted as active
		for(int tt=0;tt<=tmax-t[i];tt++){
			//printf("%i: %i active: %i\n",i,tt,calc(i-1,tt));
			ans=add(ans,mul(pw[n-i-1],mul(a[i],calc(i-1,tt))));
		}
		// Counted as active
		sm+=t[i];
		for(int tt=0;tt<=tmax-sm;tt++){
			//printf("%i: %i inactive: %i\n",i,tt,calc2(i+1,tt));
			ans=add(ans,mul(pw[i],mul(a[i],calc2(i+1,tt))));
		}
	}
	printf("%i\n",ans);
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 27ms
memory: 474892kb

input:

3 3
2 3 4
1 2 2

output:

40

result:

ok 1 number(s): "40"

Test #2:

score: 0
Accepted
time: 24ms
memory: 474940kb

input:

13 96
56231 258305 150103 164646 232643 37457 239584 192517 167805 215281 159832 98020 141006
54 1 38 1 4 1 4 11 1 4 8 22 1

output:

745634757

result:

ok 1 number(s): "745634757"

Test #3:

score: 0
Accepted
time: 24ms
memory: 474960kb

input:

14 86
205026 38691 58462 59767 205360 152715 7879 105238 33507 280429 54906 248241 102327 202931
1 49 1 1 5 12 1 5 9 18 1 1 3 32

output:

310231569

result:

ok 1 number(s): "310231569"

Test #4:

score: 0
Accepted
time: 24ms
memory: 475184kb

input:

14 85
82111 267744 229782 32542 260127 152775 1364 293699 23965 242667 264864 219673 189482 12945
1 5 1 1 2 1 38 14 1 3 4 1 21 53

output:

745175834

result:

ok 1 number(s): "745175834"

Test #5:

score: 0
Accepted
time: 19ms
memory: 474912kb

input:

15 94
119505 80865 95965 30047 68261 120903 113180 192738 220899 279742 32609 275645 38640 213859 282516
1 1 8 15 1 3 1 38 6 1 23 57 1 5 79

output:

970187257

result:

ok 1 number(s): "970187257"

Test #6:

score: 0
Accepted
time: 19ms
memory: 474968kb

input:

200 91
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

602403195

result:

ok 1 number(s): "602403195"

Test #7:

score: 0
Accepted
time: 15ms
memory: 474976kb

input:

198 87
276373 259622 211541 127475 41483 45243 254828 92569 120672 280027 180073 248960 25052 110553 136460 102137 166179 165627 29260 33966 121236 34304 67399 250912 104260 114026 261774 159285 218100 110269 112808 224799 170009 150816 34232 290942 52872 176861 177679 36123 92008 39070 265659 25497...

output:

605480487

result:

ok 1 number(s): "605480487"

Test #8:

score: -100
Time Limit Exceeded

input:

198 234111
89712 73706 49851 196942 284937 252036 155683 1073 160017 24302 1736 21240 97245 116054 17583 258181 102901 54151 14410 251885 121370 135369 278761 195054 259593 292654 222660 193579 111738 119045 14083 214343 1531 298888 25144 88309 170939 62023 113276 169190 31076 65869 121858 158901 89...

output:


result: