Submission #11138847


Source Code Expand

Copy
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
template<int MOD> struct ModInt {
    static const int Mod = MOD; unsigned x; ModInt() : x(0) { }
    ModInt(signed sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
    ModInt(signed long long sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
    int get() const { return (int)x; }
    ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
    ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }
    ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
    ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
    ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
    ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
    ModInt inverse() const { long long a = x, b = MOD, u = 1, v = 0;
        while (b) { long long t = a / b; a -= t * b; std::swap(a, b); u -= t * v; std::swap(u, v); }
        return ModInt(u); }
    bool operator==(ModInt that) const { return x == that.x; }
    bool operator!=(ModInt that) const { return x != that.x; }
    ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; }
};
template<int MOD> ostream& operator<<(ostream& st, const ModInt<MOD> a) { st << a.get(); return st; };
template<int MOD> ModInt<MOD> operator^(ModInt<MOD> a, unsigned long long k) {
    ModInt<MOD> r = 1; while (k) { if (k & 1) r *= a; a *= a; k >>= 1; } return r; }
typedef ModInt<998244353> mint;
/*---------------------------------------------------------------------------------------------------
            ∧_∧
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i     @hamayanhamayan0
    /   \     | |
    /   / ̄ ̄ ̄ ̄/  |
  __(__ニつ/     _/ .| .|____
     \/____/ (u ⊃
---------------------------------------------------------------------------------------------------*/














int N, S, A[3010];
enum { NONE, L, LR };
mint dp[3010][6010][3];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> S;
	rep(i, 0, N) cin >> A[i];

    dp[0][0][NONE] = 1;
    rep(i, 0, N) rep(sm, 0, S + 1) rep(state, 0, 3) {
        rep(nxt, state, 3) {
            dp[i + 1][sm][nxt] += dp[i][sm][state];
            if(nxt != NONE && state != LR) dp[i + 1][sm + A[i]][nxt] += dp[i][sm][state];
        }
    }
    cout << dp[N][S][LR] << endl;
}





Submission Info

Submission Time
Task F - Knapsack for All Segments
User hamayanhamayan
Language C++14 (GCC 5.4.1)
Score 600
Code Size 3499 Byte
Status AC
Exec Time 276 ms
Memory 212224 KB

Judge Result

Set Name sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 23
Set Name Test Cases
sample sample01, sample02, sample03
All 11, 12, 13, 14, 15, 21, 22, 23, 24, 25, 31, 32, 33, 34, 35, 41, 42, 43, 44, 45, sample01, sample02, sample03
Case Name Status Exec Time Memory
11 AC 63 ms 212224 KB
12 AC 64 ms 212224 KB
13 AC 64 ms 212224 KB
14 AC 64 ms 212224 KB
15 AC 63 ms 212224 KB
21 AC 70 ms 212224 KB
22 AC 148 ms 212224 KB
23 AC 129 ms 212224 KB
24 AC 155 ms 212224 KB
25 AC 76 ms 212224 KB
31 AC 139 ms 212224 KB
32 AC 166 ms 212224 KB
33 AC 159 ms 212224 KB
34 AC 162 ms 212224 KB
35 AC 162 ms 212224 KB
41 AC 276 ms 212224 KB
42 AC 275 ms 212224 KB
43 AC 274 ms 212224 KB
44 AC 275 ms 212224 KB
45 AC 274 ms 212224 KB
sample01 AC 63 ms 212224 KB
sample02 AC 63 ms 212224 KB
sample03 AC 63 ms 212224 KB