Submission #15381646


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);
    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 5038 Byte
Status
Exec Time 80 ms
Memory 7996 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 16 ms 3472 KB
a02 2 ms 3616 KB
a03 2 ms 3536 KB
a04 2 ms 3476 KB
b05 2 ms 3576 KB
b06 2 ms 3520 KB
b07 18 ms 3680 KB
b08 80 ms 7824 KB
b09 74 ms 7936 KB
b10 80 ms 7916 KB
b11 80 ms 7780 KB
b12 2 ms 3532 KB
b13 60 ms 7828 KB
b14 63 ms 7992 KB
b15 73 ms 7824 KB
b16 76 ms 7932 KB
b17 72 ms 7768 KB
b18 76 ms 7996 KB
b19 74 ms 7924 KB
b20 62 ms 7252 KB
b21 50 ms 7992 KB
b22 69 ms 7840 KB
b23 73 ms 7780 KB
b24 46 ms 6784 KB
b25 61 ms 7908 KB
b26 66 ms 7652 KB
b27 48 ms 7768 KB
b28 53 ms 7924 KB
b29 51 ms 7768 KB
b30 45 ms 5884 KB
b31 60 ms 7764 KB
b32 53 ms 7732 KB
b33 44 ms 6884 KB
b34 56 ms 7424 KB
b35 76 ms 7928 KB
b36 75 ms 7908 KB
b37 73 ms 7832 KB
b38 74 ms 7828 KB
b39 71 ms 7880 KB
b40 74 ms 7992 KB
b41 76 ms 7912 KB
b42 71 ms 7996 KB
b43 69 ms 7832 KB
b44 75 ms 7768 KB