Submission #685039

#TimeUsernameProblemLanguageResultExecution timeMemory
685039amunduzbaevMountain Trek Route (IZhO12_route)C++17
0 / 100
3 ms340 KiB
#include "bits/stdc++.h" using namespace std; #define ar array typedef long long ll; //~ #define int ll const int N = 1e6 + 5; const int MX = 2e9 + 5; int a[N]; void usaco(string s){ freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); } signed main(){ ios::sync_with_stdio(0); cin.tie(0); usaco("g"); int n, k; cin >> n >> k; set<int> on; set<ar<int, 2>> mn; for(int i=1;i<=n;i++){ cin >> a[i]; } if(a[1] != a[n]) on.insert(1); for(int i=2;i<=n;i++){ if(a[i] != a[i - 1]) on.insert(i); } auto to_l = [&](int i){ //~ for(auto x : on) cout<<x<<" "; auto it = on.lower_bound(i); //~ cout<<": "<<i<<" "<<*it<<endl; assert(it != on.end() && *it == i); if(it == on.begin()) return *--on.end(); return *--it; }; auto to_r = [&](int i){ auto it = on.upper_bound(i); if(it == on.end()) return *on.begin(); return *it; }; auto check = [&](int i){ if(a[i] < a[to_l(i)] && a[i] < a[to_r(i)]){ if(i < to_r(i)) mn.insert({to_r(i) - i, i}); else mn.insert({n - i + to_r(i), i}); } }; for(auto i : on){ check(i); } ll res = 0; while(!mn.empty()){ auto w = (*mn.begin())[0], i = (*mn.begin())[1]; int l = to_l(i), r = to_r(i); int h = min(a[l], a[r]) - a[i]; if(h * 1ll * w > k){ res += 2 * (k / w); a[i] += k / w; break; } res += 2 * h; a[i] += h; k -= h * w; mn.erase(mn.begin()); if(a[l] == a[i] && a[r] == a[i]){ on.erase(i), on.erase(r); if(!on.empty() && l != *on.begin()) check(l); } else if(a[l] == a[i]){ on.erase(i); if(!on.empty() && l != *on.begin()) check(l); } else if(a[r] == a[i]){ on.erase(r); if(!on.empty() && i != *on.begin()) check(i); } } cout<<res<<"\n"; }

Compilation message (stderr)

route.cpp: In function 'void usaco(std::string)':
route.cpp:13:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  freopen((s + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
route.cpp:14:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |  freopen((s + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...