oj.uz

Submission #1113292

# Submission time Handle Problem Language Result Execution time Memory
1113292 2024-11-16T09:52:15 Z themaver1cks Rabbit Carrot (LMIO19_triusis) C++14
14 / 100
 677 ms 262144 KB 
/**
｡∠(*・ω･)っ  ⌒ 由 ~    ((　,,・з・,,　))
 _Π_____。
/______/~＼
｜ 田田｜門｜
> 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 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[maxn_sub2];
    //
    void solve()
    {
//        for (int i=0; i<=m; ++i) dp[1][i] = (i != a[1]);
        dp[0][0] = 0;
        seg[0].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[i-1].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[i].build(1, 0, maxh, i);
        }
        cout << seg[n].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

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

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 98676 KB Output is correct
2 Correct 69 ms 98632 KB Output is correct
3 Correct 68 ms 98804 KB Output is correct
4 Correct 71 ms 99408 KB Output is correct
5 Correct 76 ms 99144 KB Output is correct
6 Correct 74 ms 99416 KB Output is correct
7 Correct 71 ms 99400 KB Output is correct
8 Correct 72 ms 99144 KB Output is correct
9 Correct 70 ms 99276 KB Output is correct
10 Correct 74 ms 99400 KB Output is correct
11 Correct 72 ms 99244 KB Output is correct
12 Correct 74 ms 99372 KB Output is correct
13 Correct 75 ms 99400 KB Output is correct
14 Correct 71 ms 99400 KB Output is correct
15 Correct 74 ms 99264 KB Output is correct
16 Correct 79 ms 99408 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 98676 KB Output is correct
2 Correct 69 ms 98632 KB Output is correct
3 Correct 68 ms 98804 KB Output is correct
4 Correct 71 ms 99408 KB Output is correct
5 Correct 76 ms 99144 KB Output is correct
6 Correct 74 ms 99416 KB Output is correct
7 Correct 71 ms 99400 KB Output is correct
8 Correct 72 ms 99144 KB Output is correct
9 Correct 70 ms 99276 KB Output is correct
10 Correct 74 ms 99400 KB Output is correct
11 Correct 72 ms 99244 KB Output is correct
12 Correct 74 ms 99372 KB Output is correct
13 Correct 75 ms 99400 KB Output is correct
14 Correct 71 ms 99400 KB Output is correct
15 Correct 74 ms 99264 KB Output is correct
16 Correct 79 ms 99408 KB Output is correct
17 Correct 76 ms 98888 KB Output is correct
18 Correct 73 ms 98888 KB Output is correct
19 Correct 77 ms 98632 KB Output is correct
20 Runtime error 677 ms 262144 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 98888 KB Output is correct
2 Correct 73 ms 98888 KB Output is correct
3 Correct 77 ms 98632 KB Output is correct
4 Runtime error 677 ms 262144 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 98888 KB Output is correct
2 Correct 73 ms 98888 KB Output is correct
3 Correct 77 ms 98632 KB Output is correct
4 Runtime error 677 ms 262144 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -