Submission #15381559


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, -inf), 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();

    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);
    cout << dp[n] << rt;

    return 0;
}

Submission Info

Submission Time
Task B - Neutralize
User ASTR1104
Language C++ (GCC 9.2.1)
Score 0
Code Size 5019 Byte
Status
Exec Time 78 ms
Memory 7980 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 7 ms 3436 KB
a02 3 ms 3460 KB
a03 3 ms 3488 KB
a04 2 ms 3476 KB
b05 2 ms 3496 KB
b06 2 ms 3488 KB
b07 18 ms 3760 KB
b08 73 ms 7856 KB
b09 75 ms 7800 KB
b10 73 ms 7764 KB
b11 77 ms 7976 KB
b12 7 ms 3492 KB
b13 61 ms 7856 KB
b14 63 ms 7828 KB
b15 70 ms 7812 KB
b16 68 ms 7732 KB
b17 76 ms 7732 KB
b18 78 ms 7860 KB
b19 72 ms 7768 KB
b20 58 ms 7360 KB
b21 56 ms 7864 KB
b22 65 ms 7824 KB
b23 66 ms 7976 KB
b24 47 ms 6740 KB
b25 59 ms 7980 KB
b26 66 ms 7980 KB
b27 48 ms 7916 KB
b28 55 ms 7852 KB
b29 52 ms 7732 KB
b30 43 ms 5768 KB
b31 65 ms 7824 KB
b32 55 ms 7464 KB
b33 47 ms 6712 KB
b34 61 ms 7388 KB
b35 69 ms 7800 KB
b36 70 ms 7828 KB
b37 72 ms 7820 KB
b38 77 ms 7820 KB
b39 70 ms 7728 KB
b40 73 ms 7892 KB
b41 71 ms 7760 KB
b42 72 ms 7820 KB
b43 72 ms 7796 KB
b44 71 ms 7856 KB