QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#354128 | #8276. Code Congestion | ucup-team134# | TL | 27ms | 475184kb | C++17 | 4.8kb | 2024-03-14 22:11:07 | 2024-03-14 22:11:08 |
Judging History
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...