Submission #1010523

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010523		vjudge1	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	23 ms	8652 KiB

Main

//
//  main.cpp
//  IntensiveCamp 2 2024
//
//  Created by Ali AlSalman on 17/05/2024.
//
 
#include <bits/stdc++.h>

#define endl '\n'

using namespace std;

//struct segment_tree {
//private:
//    int _offset;
//    vector<int> _data;
//    
//    int _query(int u, int l, int r, int qlow, int qhi) {
//        if (qlow <= l && r <= qhi) return _data[u];
//        else if (r <= qlow || qhi <= l) return 0;
//        else {
//            int m = (l + r) / 2;
//            return _query(u * 2,     l, m, qlow, qhi) +
//                   _query(u * 2 + 1, m, r, qlow, qhi);
//        }
//    }
//public:
//    segment_tree(int n) {
//        if (__builtin_popcount(n) == 1) _offset = n;
//        else _offset = (1<<(32 - __builtin_clz(n)));
//        
//        _data.resize(_offset * 2);
//    }
//    
//    void inc(int i, int val = 1) {
//        for (i += _offset; i; i /= 2) _data[i] += val;
//    }
//    
//    void inc(pair<int, int> range) {
//        auto &[l, r] = range;
//        l += _offset; r += _offset;
//        this->inc(l);
//        this->inc(r, -1);
//    }
//    
//    int query(int i) {
//        return  _query(0, 0, _offset, 0, i + 1);
//    }
//};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    
    
    int n;
    cin>>n;
    vector<long long> arr(n), dif; dif.reserve(n - 1); cin>>arr[0];
    for (int i = 1; i < n; i++) {
        cin>>arr[i];
        dif.push_back(arr[i] - arr[i - 1]);
    }
    
    vector<pair<long long, long long>> dp(n + 1);
    
    for (int i = 1; i < dp.size(); i++) {
        dp[i].first = dp[i - 1].first;
        if (i <= dif.size() && dif[i - 1] <= 0) dp[i].first += -dif[i - 1] + 1;
    }
    
    for (int i = (int) dp.size() - 2; 0 <= i; i--) {
        dp[i].second = dp[i + 1].second;
        if (0 < i && 0 <= dif[i - 1]) dp[i].second += dif[i - 1] + 1;
    }
    
    long long ans = min(max(dp[0].first, dp[0].second), max(dp.back().first, dp.back().first));
    for (int i = 2; i < n; i++) {
        ans = min(ans, max(dp[i - 1].first, dp[i].second));
    }
    
    cout<<ans<<endl;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (int i = 1; i < dp.size(); i++) {
      |                     ~~^~~~~~~~~~~
Main.cpp:68:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         if (i <= dif.size() && dif[i - 1] <= 0) dp[i].first += -dif[i - 1] + 1;
      |             ~~^~~~~~~~~~~~~

• Subtask 1: 40 / 40
• Subtask 2: 60 / 60