Submission #15381670


Source Code Expand

Copy
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using VI = vector<int>;
using VL = vector<ll>;
using VS = vector<string>;
using VB = vector<bool>;
using VVB = vector<vector<bool>>;
using VVI = vector<VI>;
using VVL = vector<VL>;
using PII = std::pair<int, int>;
using VPII = std::vector<std::pair<int, int>>;
using PLL = std::pair<ll, ll>;
using VPLL = std::vector<std::pair<ll, ll>>;
using TI3 = std::tuple<int, int, int>;
using TI4 = std::tuple<int, int, int, int>;
using TL3 = std::tuple<ll, ll, ll>;
using TL4 = std::tuple<ll, ll, ll, ll>;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n)-1; i >= 0; i--)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define rep3(i, s, n, d) for (int i = (s); i < (int)(n); i += (d))
#define allpt(v) (v).begin(), (v).end()
#define allpt_c(v) (v).cbegin(), (v).cend()
#define allpt_r(v) (v).rbegin(), (v).rend()
#define allpt_cr(v) (v).crbegin(), (v).crend()

const int mod1 = 1e9 + 7, mod2 = 998244353, mod3 = 1e9 + 9;
const int mod = mod1;
const ll inf = 1e18;

const string wsp = " ";
const string tb = "\t";
const string rt = "\n";

template <typename T>
void show1dvec(const vector<T> &v)
{
    if (v.size() == 0)
        return;
    int n = v.size() - 1;
    rep(i, n) cout << v[i] << wsp;
    cout << v[n] << rt;

    return;
}

template <typename T>
void show2dvec(const vector<vector<T>> &v)
{
    int n = v.size();
    rep(i, n) show1dvec(v[i]);
}

template <typename T, typename S>
void show1dpair(const vector<pair<T, S>> &v)
{
    int n = v.size();
    rep(i, n) cout << v[i].first << wsp << v[i].second << rt;
    return;
}

template <typename T, typename S>
void pairzip(const vector<pair<T, S>> &v, vector<T> &t, vector<T> &s)
{
    int n = v.size();
    rep(i, n)
    {
        t.push_back(v[i].first);
        s.push_back(v[i].second);
    }
    return;
}

template <typename T>
void maxvec(vector<T> &v)
{
    T s = v[0];
    int n = v.size();
    rep(i, n - 1)
    {
        if (s > v[i + 1])
        {
            v[i + 1] = s;
        }
        s = v[i + 1];
    }
}

template <typename T, typename S>
bool myfind(T t, S s)
{
    return find(t.cbegin(), t.cend(), s) != t.cend();
}

bool check(int y, int x, int h, int w)
{
    return 0 <= y && y < h && 0 <= x && x < w;
}

bool iskadomatsu(int a, int b, int c)
{
    return (a != b && b != c && c != a) && ((a > b && b < c) || (a < b && b > c));
}

VS split(string s, char c)
{
    VS ret;
    string part;
    s += c;
    rep(i, s.length())
    {
        if (s[i] == c)
        {
            ret.emplace_back(part);
            part = "";
        }
        else if (s[i] != c)
        {
            part += s[i];
        }
    }
    return ret;
}

template <typename T, typename S, typename R>
ll pow_mod(T p, S q, R mod = 1ll)
{
    ll ret = 1, r = p;
    while (q)
    {
        if (q % 2)
            ret *= r, ret %= mod;
        r = (r * r) % mod, q /= 2;
    }
    return ret % mod;
}

template <typename T, typename S>
ll pow_no_mod(T p, S q)
{
    ll ret = 1, r = p;
    while (q)
    {
        if (q % 2)
            ret *= r;
        r = (r * r), q /= 2;
    }
    return ret;
}

void make_frac_tables(VL &frac_list, VL &frac_inv_list)
{
    rep(i, frac_list.size() - 1)
    {
        frac_list[i + 1] *= frac_list[i] * (i + 1);
        frac_list[i + 1] %= mod;
        frac_inv_list[i + 1] *= frac_inv_list[i] * pow_mod(i + 1, mod - 2, mod);
        frac_inv_list[i + 1] %= mod;
    }
}

ll comb(int a, int b, const VL &frac_list, const VL &frac_inv_list)
{
    if (a < b)
        return 0;
    if (b < 0)
        return 0;
    ll ret = frac_list[a];
    ret *= frac_inv_list[b];
    ret %= mod;
    ret *= frac_inv_list[a - b];
    ret %= mod;
    return ret;
}



int main()
{

    // cin.tie(0);
    // ios::sync_with_stdio(false);

#ifdef DEBUG
    cout << "DEBUG MODE" << endl;
    ifstream in("input.txt"); //for debug
    cin.rdbuf(in.rdbuf());    //for debug
#endif

    int n, k;
    cin >> n >> k;
    ll p;
    VL dp(n + 1, 0), num(n);
    dp[0] = 0;
    rep(i, n)
    {
        cin >> num[i];
    }

    num.emplace_back(1);
    rep(i, n)
    {
        if (num[i] <= 0)
        {
            auto j = i, m = 0;
            while(num[j] < 0)
            {
                m++;
                j++;
            }
            if (m >= k)
            {
                rep(j, m)
                {
                    num[i + j] = 0;
                }
            }
            i += m;
        }
    }
    num.pop_back();
    // show1dvec(num);

    rep(i, n)
    {
        p = num[i];
        dp[i + 1] = dp[i] + p;
        if (i + 1 - k >= 0)
        {
            dp[i + 1] = max(dp[i + 1], dp[i + 1 - k]);
        }
    }
    // show1dvec(dp);
    auto ans = max<ll>(dp[n], 0ll);
    cout << ans << rt;

    return 0;
}

Submission Info

Submission Time
Task B - Neutralize
User ASTR1104
Language C++ (GCC 9.2.1)
Score 0
Code Size 5075 Byte
Status
Exec Time 86 ms
Memory 7992 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 a01, a02, a03, a04
All 0 / 400 a01, a02, a03, a04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23, b24, b25, b26, b27, b28, b29, b30, b31, b32, b33, b34, b35, b36, b37, b38, b39, b40, b41, b42, b43, b44
Case Name Status Exec Time Memory
a01 2 ms 3444 KB
a02 2 ms 3576 KB
a03 1 ms 3568 KB
a04 3 ms 3472 KB
b05 2 ms 3472 KB
b06 2 ms 3580 KB
b07 16 ms 3612 KB
b08 86 ms 7876 KB
b09 77 ms 7756 KB
b10 75 ms 7992 KB
b11 80 ms 7928 KB
b12 9 ms 3520 KB
b13 58 ms 7932 KB
b14 59 ms 7816 KB
b15 72 ms 7836 KB
b16 74 ms 7872 KB
b17 75 ms 7812 KB
b18 73 ms 7884 KB
b19 75 ms 7836 KB
b20 62 ms 7224 KB
b21 59 ms 7880 KB
b22 68 ms 7780 KB
b23 76 ms 7820 KB
b24 42 ms 6872 KB
b25 63 ms 7984 KB
b26 66 ms 7512 KB
b27 54 ms 7840 KB
b28 59 ms 7516 KB
b29 48 ms 7992 KB
b30 43 ms 5792 KB
b31 64 ms 7836 KB
b32 59 ms 7616 KB
b33 47 ms 6720 KB
b34 61 ms 7400 KB
b35 80 ms 7816 KB
b36 74 ms 7840 KB
b37 74 ms 7900 KB
b38 71 ms 7808 KB
b39 77 ms 7752 KB
b40 73 ms 7840 KB
b41 74 ms 7776 KB
b42 73 ms 7884 KB
b43 77 ms 7756 KB
b44 74 ms 7836 KB