oj.uz

Submission #1113296

# Submission time Handle Problem Language Result Execution time Memory
1113296 2024-11-16T09:53:49 Z themaver1cks Rabbit Carrot (LMIO19_triusis) C++14
14 / 100
 1000 ms 98712 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;
    //
    void solve()
    {
//        for (int i=0; i<=m; ++i) dp[1][i] = (i != a[1]);
        dp[0][0] = 0;
        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.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: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 69 ms 98644 KB Output is correct
2 Correct 80 ms 98480 KB Output is correct
3 Correct 73 ms 98464 KB Output is correct
4 Correct 76 ms 98568 KB Output is correct
5 Correct 83 ms 98704 KB Output is correct
6 Correct 84 ms 98632 KB Output is correct
7 Correct 71 ms 98640 KB Output is correct
8 Correct 78 ms 98460 KB Output is correct
9 Correct 80 ms 98632 KB Output is correct
10 Correct 79 ms 98632 KB Output is correct
11 Correct 69 ms 98536 KB Output is correct
12 Correct 74 ms 98636 KB Output is correct
13 Correct 75 ms 98644 KB Output is correct
14 Correct 74 ms 98632 KB Output is correct
15 Correct 70 ms 98616 KB Output is correct
16 Correct 78 ms 98636 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 98644 KB Output is correct
2 Correct 80 ms 98480 KB Output is correct
3 Correct 73 ms 98464 KB Output is correct
4 Correct 76 ms 98568 KB Output is correct
5 Correct 83 ms 98704 KB Output is correct
6 Correct 84 ms 98632 KB Output is correct
7 Correct 71 ms 98640 KB Output is correct
8 Correct 78 ms 98460 KB Output is correct
9 Correct 80 ms 98632 KB Output is correct
10 Correct 79 ms 98632 KB Output is correct
11 Correct 69 ms 98536 KB Output is correct
12 Correct 74 ms 98636 KB Output is correct
13 Correct 75 ms 98644 KB Output is correct
14 Correct 74 ms 98632 KB Output is correct
15 Correct 70 ms 98616 KB Output is correct
16 Correct 78 ms 98636 KB Output is correct
17 Correct 77 ms 98636 KB Output is correct
18 Correct 66 ms 98684 KB Output is correct
19 Correct 69 ms 98632 KB Output is correct
20 Correct 973 ms 98632 KB Output is correct
21 Execution timed out 1073 ms 98712 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 98636 KB Output is correct
2 Correct 66 ms 98684 KB Output is correct
3 Correct 69 ms 98632 KB Output is correct
4 Correct 973 ms 98632 KB Output is correct
5 Execution timed out 1073 ms 98712 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 98636 KB Output is correct
2 Correct 66 ms 98684 KB Output is correct
3 Correct 69 ms 98632 KB Output is correct
4 Correct 973 ms 98632 KB Output is correct
5 Execution timed out 1073 ms 98712 KB Time limit exceeded
6 Halted 0 ms 0 KB -