Submission #57539287

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

int n;
long long k;
long long pre[200005];
map<long long, int> m;
int dp[200005];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
		cin >> pre[i];
	for (int i = 1, tot = dp[0] = m[0] = 1; i <= n; i++) {
		dp[i] = tot;
		if ((dp[i] -= m[(pre[i] += pre[i - 1]) - k]) < 0)
			dp[i] += MOD;
		if ((m[pre[i]] += dp[i]) >= MOD)
			m[pre[i]] -= MOD;
		if ((tot += dp[i]) >= MOD)
			tot -= MOD;
	}
	cout << dp[n] << '\n';
	return 0;
}

Submission Info

Submission Time
Task E - Avoid K Partition
User woruo27
Language C++ 17 (gcc 12.2)
Score 475
Code Size 594 Byte
Status AC
Exec Time 182 ms
Memory 30904 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 3404 KiB
00_sample_01.txt AC 1 ms 3404 KiB
00_sample_02.txt AC 1 ms 3432 KiB
01_small_00.txt AC 1 ms 3476 KiB
01_small_01.txt AC 1 ms 3604 KiB
01_small_02.txt AC 1 ms 3496 KiB
01_small_03.txt AC 1 ms 3536 KiB
01_small_04.txt AC 1 ms 3536 KiB
01_small_05.txt AC 1 ms 3404 KiB
01_small_06.txt AC 1 ms 3396 KiB
01_small_07.txt AC 1 ms 3548 KiB
01_small_08.txt AC 1 ms 3464 KiB
01_small_09.txt AC 1 ms 3536 KiB
02_random_00.txt AC 83 ms 23660 KiB
02_random_01.txt AC 3 ms 3744 KiB
02_random_02.txt AC 73 ms 18108 KiB
02_random_03.txt AC 18 ms 5336 KiB
02_random_04.txt AC 94 ms 20912 KiB
02_random_05.txt AC 10 ms 4416 KiB
02_random_06.txt AC 15 ms 7160 KiB
02_random_07.txt AC 19 ms 5176 KiB
02_random_08.txt AC 41 ms 15640 KiB
02_random_09.txt AC 16 ms 4876 KiB
03_max_00.txt AC 117 ms 30808 KiB
03_max_01.txt AC 31 ms 6268 KiB
03_max_02.txt AC 122 ms 30824 KiB
03_max_03.txt AC 31 ms 6304 KiB
03_max_04.txt AC 182 ms 30704 KiB
03_max_05.txt AC 29 ms 5968 KiB
03_max_06.txt AC 64 ms 18324 KiB
03_max_07.txt AC 30 ms 6152 KiB
03_max_08.txt AC 123 ms 30904 KiB
03_max_09.txt AC 30 ms 6064 KiB
04_min_00.txt AC 1 ms 3508 KiB
04_min_01.txt AC 1 ms 3496 KiB
05_hack_00.txt AC 8 ms 5764 KiB
05_hack_01.txt AC 9 ms 5772 KiB