Submission #1113291

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113291		themaver1cks	Rabbit Carrot (LMIO19_triusis)	C++14	14 / 100	1042 ms	98736 KiB

triusis

/**
｡∠(*・ω･)っ  ⌒ 由 ~    ((　,,・з・,,　))
 _Π_____。
/______/~＼
｜ 田田｜門｜
> love miku so muchhhh <3
**/
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define el "\n"

typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
// var dec
const int maxn = 2e5 + 3;
const int inf_int = 1e9;
int n, m;
// ds dec
int a[maxn];
//
namespace sub2
{
    const int maxn_sub2 = 5e3 + 3;
    const int maxh = 5000;
    vector <vector<int>> dp(maxn_sub2, vector<int>(maxn_sub2, inf_int));
    //
    struct SegmentTree
    {
        int st[4*maxn_sub2];
        //
        void init()
        {
            memset(st, 0, sizeof(st));
        }
        //
        void build(int id, int l, int r, int ind)
        {
            if (l == r)
            {
                st[id] = dp[ind][l];
                return;
            }
            //
            int mid = (l+r) >> 1;
            build(id<<1, l, mid, ind);
            build(id<<1|1, mid+1, r, ind);
            st[id] = min(st[id<<1], st[id<<1|1]);
        }
        //
        int get(int id, int l, int r, int lx, int rx)
        {
            if (lx <= l && r <= rx) return st[id];
            if (rx < l || r < lx) return inf_int;
            //
            int mid = (l+r) >> 1;
            int v1 = get(id<<1, l, mid, lx, rx);
            int v2 = get(id<<1|1, mid+1, r, lx, rx);
            return min(v1, v2);
        }
    } seg;
    //
    void solve()
    {
//        for (int i=1; i<=m; ++i) dp[1][i] = (i != a[1]);
        dp[0][0] = 0;
        seg.init();
        seg.build(1, 0, maxh, 0);
        for (int i=1; i<=n; ++i)
        {
//            cout << i << el;
            for (int j=0; j<=maxh; ++j)
            {
                dp[i][j] = seg.get(1, 0, maxh, max(0, j-m), maxh) + (j != a[i]);
                dp[i][j] = min(dp[i][j], inf_int);
            }
//            for (int j=0; j<=10; ++j) cout << j << " " << dp[i][j] << el;
//            cout << el;
            seg.init();
            seg.build(1, 0, maxh, i);
        }
        cout << seg.get(1, 0, maxh, 0, maxh) << el;
    }
}
//
void solve()
{
    cin >> n >> m;
    for (int i=1; i<=n; ++i) cin >> a[i];
    sub2::solve();
}
//
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("lmao.inp", "r"))
    {
        freopen("lmao.inp", "r", stdin);
        freopen("lmao.out", "w", stdout);
    }
    int t = 1;
//    cin >> t;
    while (t--) solve();
    return 0;
}

Compilation message (stderr)

triusis.cpp: In function 'int32_t main()':
triusis.cpp:104:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         freopen("lmao.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
triusis.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen("lmao.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 0 / 21
• Subtask 3: 0 / 28
• Subtask 4: 0 / 37