Submission #57586742

Source Code Expand

// E - Avoid K Partition 
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

constexpr ll MOD = 998244353;

int main()
{
	int n;
	ll K;
	cin >> n >> K;
	vector<ll> a(n + 1), sum(n + 1), f(n + 1);
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i];
		sum[i] = sum[i-1] + a[i];
	}
	
	f[0] = 1;
	ll all = 1;
	map<ll, ll> mp;
	mp[0] = 1;
	for(int i = 1; i <= n; i++)
	{
		f[i] = ((all - mp[sum[i] - K]) % MOD + MOD) % MOD;
		all = (all + f[i]) % MOD;
		mp[sum[i]] = (mp[sum[i]] + f[i]) % MOD;
	}
	
	cout << f[n] << endl;
	
	return 0;
}

Submission Info

Submission Time
Task E - Avoid K Partition
User dengstar
Language C++ 17 (gcc 12.2)
Score 475
Code Size 580 Byte
Status AC
Exec Time 192 ms
Memory 32716 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 475 / 475
Status
AC × 3
AC × 37
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_small_00.txt, 01_small_01.txt, 01_small_02.txt, 01_small_03.txt, 01_small_04.txt, 01_small_05.txt, 01_small_06.txt, 01_small_07.txt, 01_small_08.txt, 01_small_09.txt, 02_random_00.txt, 02_random_01.txt, 02_random_02.txt, 02_random_03.txt, 02_random_04.txt, 02_random_05.txt, 02_random_06.txt, 02_random_07.txt, 02_random_08.txt, 02_random_09.txt, 03_max_00.txt, 03_max_01.txt, 03_max_02.txt, 03_max_03.txt, 03_max_04.txt, 03_max_05.txt, 03_max_06.txt, 03_max_07.txt, 03_max_08.txt, 03_max_09.txt, 04_min_00.txt, 04_min_01.txt, 05_hack_00.txt, 05_hack_01.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 1 ms 3484 KiB
00_sample_01.txt AC 1 ms 3532 KiB
00_sample_02.txt AC 1 ms 3540 KiB
01_small_00.txt AC 1 ms 3588 KiB
01_small_01.txt AC 1 ms 3540 KiB
01_small_02.txt AC 1 ms 3488 KiB
01_small_03.txt AC 1 ms 3492 KiB
01_small_04.txt AC 1 ms 3480 KiB
01_small_05.txt AC 1 ms 3492 KiB
01_small_06.txt AC 1 ms 3648 KiB
01_small_07.txt AC 1 ms 3460 KiB
01_small_08.txt AC 1 ms 3528 KiB
01_small_09.txt AC 1 ms 3520 KiB
02_random_00.txt AC 110 ms 25152 KiB
02_random_01.txt AC 4 ms 4008 KiB
02_random_02.txt AC 86 ms 19168 KiB
02_random_03.txt AC 28 ms 6380 KiB
02_random_04.txt AC 103 ms 22164 KiB
02_random_05.txt AC 16 ms 4656 KiB
02_random_06.txt AC 28 ms 7320 KiB
02_random_07.txt AC 30 ms 6380 KiB
02_random_08.txt AC 59 ms 16012 KiB
02_random_09.txt AC 24 ms 5792 KiB
03_max_00.txt AC 147 ms 32660 KiB
03_max_01.txt AC 47 ms 8112 KiB
03_max_02.txt AC 157 ms 32716 KiB
03_max_03.txt AC 47 ms 8376 KiB
03_max_04.txt AC 192 ms 32648 KiB
03_max_05.txt AC 45 ms 8152 KiB
03_max_06.txt AC 113 ms 20372 KiB
03_max_07.txt AC 47 ms 8176 KiB
03_max_08.txt AC 146 ms 32632 KiB
03_max_09.txt AC 48 ms 8320 KiB
04_min_00.txt AC 1 ms 3516 KiB
04_min_01.txt AC 1 ms 3408 KiB
05_hack_00.txt AC 21 ms 7960 KiB
05_hack_01.txt AC 22 ms 7864 KiB