Submission #1237824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237824		warlock	Rabbit Carrot (LMIO19_triusis)	C++17	0 / 100	3 ms	5192 KiB

triusis

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define ll long long
#define int long long int
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define all(x) begin(x),end(x)
#define rev(x) rbegin(x),rend(x)
#define min_priority_queue(x) priority_queue<x, vector<x>,greater<x>>
const int MOD = 1000000007;
const int INF = 1e18;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

void arrin(vi&x,int n){ for(int i=0;i<n;i++){cin >> x[i];}}
void arrout(vi&x){ for(int i=0;i<x.size();i++){cout<< x[i]<<" ";}cout<< endl;}
void pr_bool(bool i){ cout << (i ? "YES" : "NO") << endl;}

int gcd(int a,int b){ if(b==0) return a; return gcd(b, a%b);}
int lcm(int a,int b){ return a/gcd(a,b)*b;}

int N,M;
int towers[200005]; 
int dp[200005][3];
int solve(int next_pole,int curr_high,int last_oper){
    if(next_pole == N) return 0;
    if(last_oper != -1 && dp[next_pole][last_oper] != -1) return dp[next_pole][last_oper];
    int ans = LLONG_MAX;
    if(towers[next_pole]-curr_high <= M){
        ans = min(ans,solve(next_pole+1,towers[next_pole],0));
    }
    if(curr_high + M > towers[next_pole]){
        ans = min(ans,1 + solve(next_pole+1, curr_high+M,1));
    }
    if(curr_high + M < towers[next_pole]){
        ans = min(ans,1 + solve(next_pole+1,curr_high+M,2));
    }
    if(last_oper != -1) return dp[next_pole][last_oper] = ans;
    return ans; 
}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> N >> M;
    for(int i = 0;i < N;i++){
        cin >> towers[i];
    }
    memset(dp,-1,sizeof(dp));
    cout << solve(0,0,-1) << endl;
    // for(int i = 0;i < N;i++){
    //     for(int j = 0;j < 3;j++){
    //         cout << dp[i][j] << " ";
    //     }
    //     cout << endl;
    // }
}
// 02:17:58

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