Submission #15381186


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;
                }
            }
        }
    }
    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 4998 Byte
Status
Exec Time 2205 ms
Memory 7944 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 3460 KB
a02 2 ms 3500 KB
a03 2 ms 3528 KB
a04 2 ms 3548 KB
b05 2 ms 3600 KB
b06 2 ms 3528 KB
b07 15 ms 3636 KB
b08 81 ms 7932 KB
b09 76 ms 7912 KB
b10 80 ms 7900 KB
b11 78 ms 7932 KB
b12 6 ms 3604 KB
b13 2205 ms 7804 KB
b14 2205 ms 7924 KB
b15 70 ms 7896 KB
b16 72 ms 7768 KB
b17 76 ms 7892 KB
b18 94 ms 7916 KB
b19 164 ms 7904 KB
b20 57 ms 7280 KB
b21 55 ms 7892 KB
b22 68 ms 7928 KB
b23 91 ms 7836 KB
b24 48 ms 6808 KB
b25 101 ms 7892 KB
b26 76 ms 7544 KB
b27 48 ms 7760 KB
b28 51 ms 7904 KB
b29 54 ms 7944 KB
b30 40 ms 5692 KB
b31 62 ms 7768 KB
b32 55 ms 7672 KB
b33 46 ms 6780 KB
b34 60 ms 7280 KB
b35 73 ms 7916 KB
b36 71 ms 7776 KB
b37 77 ms 7764 KB
b38 75 ms 7768 KB
b39 77 ms 7764 KB
b40 74 ms 7916 KB
b41 75 ms 7896 KB
b42 77 ms 7836 KB
b43 72 ms 7776 KB
b44 75 ms 7892 KB