Submission #1010523

#TimeUsernameProblemLanguageResultExecution timeMemory
1010523vjudge1Growing Vegetables is Fun 4 (JOI21_ho_t1)C++17
100 / 100
23 ms8652 KiB
// // 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;
      |             ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...