結果
問題 | No.2625 Bouns Ai |
ユーザー |
![]() |
提出日時 | 2024-02-09 21:55:49 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 198 ms / 2,000 ms |
コード長 | 2,256 bytes |
コンパイル時間 | 1,410 ms |
コンパイル使用メモリ | 173,532 KB |
実行使用メモリ | 161,644 KB |
最終ジャッジ日時 | 2024-09-28 15:12:10 |
合計ジャッジ時間 | 6,241 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll =long long;#define all(v) v.begin(),v.end()#define rep(i,a,b) for(int i=a;i<b;i++)#define rrep(i,a,b) for(int i=a;i>=b;i--)ll INF=2e18;const int mod = 998244353;class mint {long long x;public:mint(long long x=0) : x((x%mod+mod)%mod) {}mint operator-() const {return mint(-x);}mint& operator+=(const mint& a) {if ((x += a.x) >= mod) x -= mod;return *this;}mint& operator-=(const mint& a) {if ((x += mod-a.x) >= mod) x -= mod;return *this;}mint& operator*=(const mint& a) {(x *= a.x) %= mod;return *this;}mint operator+(const mint& a) const {mint res(*this);return res+=a;}mint operator-(const mint& a) const {mint res(*this);return res-=a;}mint operator*(const mint& a) const {mint res(*this);return res*=a;}mint pow(ll t) const {if (!t) return 1;mint a = pow(t>>1);a *= a;if (t&1) a *= *this;return a;}// for prime modmint inv() const {return pow(mod-2);}mint& operator/=(const mint& a) {return (*this) *= a.inv();}mint operator/(const mint& a) const {mint res(*this);return res/=a;}friend ostream& operator<<(ostream& os, const mint& m){os << m.x;return os;}};int main() {ios::sync_with_stdio(false);cin.tie(0);ll N;cin>>N;vector<ll> A(N);for(ll i=0;i<N;i++) cin>>A[i];/*dp[i][j]=0~i人で,Bi=jの時の真のスコアのとり方の総数.dp[i][j]+=dp[i-1][0]~dp[i-1][r],rはj以下でかつ,A[i]+j>=A[i-1]+r*/vector<vector<mint>> dp(N,vector<mint> (100000+10));for(ll i=0;i+A[0]<=100000;i++) {dp[0][i]=1;}ll ma=100000;vector<mint> r(ma+10);for(ll i=0;i<=ma;i++) {r[i]+=dp[0][i];if(i>0) r[i]+=r[i-1];}for(ll i=1;i<N;i++) {for(ll j=0;j+A[i]<=ma;j++) {ll s=j+A[i];s-=A[i-1];if(s>=0) {s=min(s,j);dp[i][j]+=r[s];}}r=vector<mint> (ma+10);for(ll j=0;j<=ma;j++) {r[j]+=dp[i][j];if(j>0) r[j]+=r[j-1];}}cout<<r[ma]<<endl;}