제출 #1205447

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1205447		ofoz	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	229 ms	23852 KiB

triusis

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define vi vector<int>
vi tree;

void update(int v, int tl, int tr, int p, int k) {
    if (tl == tr) tree[v] = min(tree[v], k);
    else {
        int tm = (tl+tr)/2;
        if (p <= tm) update(2*v, tl, tm, p, k);
        else update(2*v+1, tm+1, tr, p, k);
        tree[v] = min(tree[2*v], tree[2*v+1]);
    }
}

int query(int v, int tl, int tr, int l, int r) {
    if (l > r) return INT32_MAX;
    if (tl == l && tr == r) return tree[v];
    int tm = (tl+tr)/2;
    int a = query(2*v, tl, tm, l, min(r, tm));
    int b = query(2*v+1, tm+1, tr, max(l, tm+1), r);
    return min(a, b);
}

void solve() {
    int n, m;
    cin >> n >> m;
    
    vector<int> a(n);
    for (int &x : a) cin >> x;
    a.insert(a.begin(), 0);
    a.push_back(INT32_MIN);
    n += 2;
    tree.resize(4*n, INT32_MAX);
    vi s;
    for (int i = 0; i < n; i++) {
        s.push_back(a[i] - m * i);
    }
    map<int, int> comp;
    sort(s.begin(), s.end());
    int ind = 0;
    for (int i = 0; i < n; i++) {
        if (comp.count(s[i])) continue;
        comp[s[i]] = ind;
        ind++;
    }
    vi dp(n, INT32_MAX);
    dp[0] = 0;
    update(1, 0, n-1, comp[0], 0);
    for (int i = 1; i < n; i++) {
        if (a[i] - a[i-1] <= m) dp[i] = dp[i-1];

        int ind = comp[(a[i] - m * i)];
        int x = query(1, 0, n-1, ind, n-1);
        
        dp[i] = min(dp[i], x + i - 1);
        
        update(1, 0, n-1, ind, dp[i] - i);
        // cerr << i << ' ' << x << ' ' << dp[i] << endl;
    }
    cout << dp[n-1];
}

/*
a_i - a_j <= (i - j) * m
a_i - a_j <= mi - mj
a_i - mi <= a_j - mj

200 - 1200 >= 1000 - 1600
dp_j + (i - j)
dp_j - j
look for index j such that:
dp_j - j is minimized
a_i - mi <= a_j - mj
*/

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
}

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