Submission #13819478


Source Code Expand

Copy
#include<bits/stdc++.h>
using namespace std;
using UL = unsigned int;
using ULL = unsigned long long;
using LL = long long;
#define rep(i, n) for(UL i = 0; i < (n); i++)

struct Problem {
public:
	UL N, S;
	UL A[3000];
	static const ULL M = 998244353;
	ULL dp[3001][3001] = {};
	static const ULL i2 = 998244353 / 2 + 1;

	void Solve() {
		scanf("%u%u", &N, &S);
		rep(i, N) scanf("%u", A + i);
		dp[0][0] = 1;
		rep(i, N) {
			rep(j, S + 1) dp[i + 1][j] = dp[i][j];
			for (UL j = A[i]; j <= S; j++) {
				dp[i + 1][j] += dp[i][j - A[i]] * i2;
				dp[i + 1][j] %= M;
			}
		}
		ULL mul = 1;
		rep(i, N) mul = mul * 2 % M;
		ULL ans = dp[N][S] * mul % M;
		cout << ans << endl;
	}
};

int main() {
	unique_ptr<Problem> p(new Problem());
	p->Solve();
	return 0;
}

Submission Info

Submission Time
Task F - Knapsack for All Subsets
User Nachia
Language C++ (GCC 9.2.1)
Score 600
Code Size 800 Byte
Status AC
Exec Time 81 ms
Memory 73568 KB

Compile Error

./Main.cpp: In member function ‘void Problem::Solve()’:
./Main.cpp:17:8: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   17 |   scanf("%u%u", &N, &S);
      |   ~~~~~^~~~~~~~~~~~~~~~
./Main.cpp:18:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   18 |   rep(i, N) scanf("%u", A + i);
      |             ~~~~~^~~~~~~~~~~~~

Judge Result

Set Name sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 27
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, 51, 52, 53, 54, sample01, sample02, sample03
Case Name Status Exec Time Memory
11 AC 59 ms 73568 KB
12 AC 56 ms 73452 KB
13 AC 55 ms 73348 KB
14 AC 57 ms 73568 KB
15 AC 60 ms 73512 KB
21 AC 59 ms 73564 KB
22 AC 62 ms 73528 KB
23 AC 62 ms 73564 KB
24 AC 60 ms 73556 KB
25 AC 56 ms 73552 KB
31 AC 63 ms 73420 KB
32 AC 66 ms 73472 KB
33 AC 68 ms 73392 KB
34 AC 65 ms 73564 KB
35 AC 65 ms 73392 KB
41 AC 78 ms 73416 KB
42 AC 75 ms 73472 KB
43 AC 76 ms 73460 KB
44 AC 81 ms 73472 KB
45 AC 79 ms 73484 KB
51 AC 55 ms 73396 KB
52 AC 54 ms 73440 KB
53 AC 57 ms 73396 KB
54 AC 55 ms 73416 KB
sample01 AC 55 ms 73472 KB
sample02 AC 54 ms 73552 KB
sample03 AC 55 ms 73556 KB