Submission #591046

#	Time	Username	Problem	Language	Result	Execution time	Memory
591046		bLIC	Rabbit Carrot (LMIO19_triusis)	C++17	0 / 100	1 ms	212 KiB

triusis

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

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x).size()
#define ft first
#define sd second
#define pb push_back
#define endl '\n'

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef pair<ll, ll> pll;
typedef vector<pll> vll;
typedef vector<vi> vvi;

#define dbg if(1)

void printbit(int x) {string s="\n";while(x){s=((x%2)?'1':'0')+s;x/=2;} cout<<s;}

const ll MOD = 1e9+7;
const int INF = 1e9;
const int N = 200001;


void solve(){
    int n, m;
    cin>>n>>m;

    int a[n+1]{};
    for (int i =0;i<n;i++) cin>>a[i+1];

    int dp[n+1][2];
    int upd[n+1];
    for (int i = 1;i<=n;i++) upd[i] = a[i-1];

    for (int i = 1;i<=n;i++){
        if (a[i]-a[i-1]>m){
            if (a[i]-upd[i-1]>m) dp[i][0] = INF;
            else {
                dp[i][0] = dp[i-1][1];
            }
        }
        else {
            dp[i][0] = dp[i-1][0];
        }

        if (dp[i-1][1]<=dp[i-1][0]){
            dp[i][1] = dp[i-1][1]+1;
            upd[i] = upd[i-1]+m;
        }
        else {
            dp[i][1] = dp[i-1][0]+1;
            upd[i] = upd[i-1]+m;
        }
    }
    cout<<min(dp[n][0], dp[n][1]);
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t = 1;
    // cin>>t;

    while(t--){

        solve();
        cout<<endl;
    }
}

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