oj.uz

Submission #1113291

# Submission time Handle Problem Language Result Execution time Memory
1113291 2024-11-16T09:49:50 Z themaver1cks Rabbit Carrot (LMIO19_triusis) C++14
14 / 100
 1000 ms 98736 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 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

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 98632 KB Output is correct
2 Correct 85 ms 98624 KB Output is correct
3 Correct 80 ms 98632 KB Output is correct
4 Correct 79 ms 98524 KB Output is correct
5 Correct 88 ms 98632 KB Output is correct
6 Correct 79 ms 98632 KB Output is correct
7 Correct 85 ms 98488 KB Output is correct
8 Correct 75 ms 98632 KB Output is correct
9 Correct 80 ms 98700 KB Output is correct
10 Correct 78 ms 98632 KB Output is correct
11 Correct 78 ms 98632 KB Output is correct
12 Correct 75 ms 98536 KB Output is correct
13 Correct 79 ms 98632 KB Output is correct
14 Correct 78 ms 98632 KB Output is correct
15 Correct 89 ms 98644 KB Output is correct
16 Correct 89 ms 98496 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 98632 KB Output is correct
2 Correct 85 ms 98624 KB Output is correct
3 Correct 80 ms 98632 KB Output is correct
4 Correct 79 ms 98524 KB Output is correct
5 Correct 88 ms 98632 KB Output is correct
6 Correct 79 ms 98632 KB Output is correct
7 Correct 85 ms 98488 KB Output is correct
8 Correct 75 ms 98632 KB Output is correct
9 Correct 80 ms 98700 KB Output is correct
10 Correct 78 ms 98632 KB Output is correct
11 Correct 78 ms 98632 KB Output is correct
12 Correct 75 ms 98536 KB Output is correct
13 Correct 79 ms 98632 KB Output is correct
14 Correct 78 ms 98632 KB Output is correct
15 Correct 89 ms 98644 KB Output is correct
16 Correct 89 ms 98496 KB Output is correct
17 Correct 80 ms 98652 KB Output is correct
18 Correct 77 ms 98632 KB Output is correct
19 Correct 75 ms 98632 KB Output is correct
20 Correct 922 ms 98736 KB Output is correct
21 Execution timed out 1042 ms 98632 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 98652 KB Output is correct
2 Correct 77 ms 98632 KB Output is correct
3 Correct 75 ms 98632 KB Output is correct
4 Correct 922 ms 98736 KB Output is correct
5 Execution timed out 1042 ms 98632 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 98652 KB Output is correct
2 Correct 77 ms 98632 KB Output is correct
3 Correct 75 ms 98632 KB Output is correct
4 Correct 922 ms 98736 KB Output is correct
5 Execution timed out 1042 ms 98632 KB Time limit exceeded
6 Halted 0 ms 0 KB -