Submission #57538962

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;
using namespace __gnu_pbds;
using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
using trii = tuple<int, int, int>;

constexpr ll mod = 998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    ll k;
    cin >> n >> k;
    ll a[n], p[n + 1], rs = 1, dp[n + 1];
    p[0] = 0, memset(dp, 0, sizeof dp), dp[0] = 1;
    for(int i = 0;i<n;++i) {
        cin >> a[i];
        p[i + 1] = p[i] + a[i];
    }
    map<ll, ll> t;
    t[0] = 1;
    for(int i = 1;i<=n;++i) {
        dp[i] = (rs - t[p[i] - k] + mod)%mod, rs = (rs + dp[i])%mod, t[p[i]] = (t[p[i]] + dp[i])%mod;
    }
    cout << dp[n] << endl;
    return 0;
}

Submission Info

Submission Time
Task E - Avoid K Partition
User blank_stare
Language C++ 20 (gcc 12.2)
Score 475
Code Size 1027 Byte
Status AC
Exec Time 209 ms
Memory 33244 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 3572 KiB
00_sample_01.txt AC 1 ms 3420 KiB
00_sample_02.txt AC 1 ms 3476 KiB
01_small_00.txt AC 1 ms 3552 KiB
01_small_01.txt AC 1 ms 3676 KiB
01_small_02.txt AC 1 ms 3468 KiB
01_small_03.txt AC 1 ms 3532 KiB
01_small_04.txt AC 1 ms 3472 KiB
01_small_05.txt AC 1 ms 3552 KiB
01_small_06.txt AC 1 ms 3464 KiB
01_small_07.txt AC 1 ms 3556 KiB
01_small_08.txt AC 1 ms 3476 KiB
01_small_09.txt AC 1 ms 3612 KiB
02_random_00.txt AC 96 ms 25244 KiB
02_random_01.txt AC 3 ms 3900 KiB
02_random_02.txt AC 83 ms 19444 KiB
02_random_03.txt AC 21 ms 6520 KiB
02_random_04.txt AC 107 ms 22632 KiB
02_random_05.txt AC 12 ms 5152 KiB
02_random_06.txt AC 19 ms 7948 KiB
02_random_07.txt AC 21 ms 6844 KiB
02_random_08.txt AC 49 ms 16552 KiB
02_random_09.txt AC 18 ms 6120 KiB
03_max_00.txt AC 133 ms 33112 KiB
03_max_01.txt AC 34 ms 8532 KiB
03_max_02.txt AC 140 ms 33244 KiB
03_max_03.txt AC 34 ms 8720 KiB
03_max_04.txt AC 209 ms 33192 KiB
03_max_05.txt AC 32 ms 8288 KiB
03_max_06.txt AC 78 ms 20696 KiB
03_max_07.txt AC 33 ms 8520 KiB
03_max_08.txt AC 141 ms 33088 KiB
03_max_09.txt AC 34 ms 8444 KiB
04_min_00.txt AC 1 ms 3428 KiB
04_min_01.txt AC 1 ms 3468 KiB
05_hack_00.txt AC 10 ms 8248 KiB
05_hack_01.txt AC 11 ms 8196 KiB