fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. const ll INF = (ll)4e14; // 이전 4e18 → 4e14로 변경
  5.  
  6. int main() {
  7.     ios::sync_with_stdio(0);
  8.     cin.tie(0);
  9.  
  10.     int N;
  11.     if (!(cin >> N)) return 0;
  12.  
  13.     vector<ll> T(N), c(N, INF);
  14.     priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> q;
  15.  
  16.     for (int i = 0; i < N; i++) {
  17.         cin >> T[i];
  18.         c[i] = T[i];
  19.         q.push({c[i], i});
  20.     }
  21.  
  22.     while (!q.empty()) {
  23.         auto [t, u] = q.top(); 
  24.         q.pop();
  25.         if (t != c[u]) continue;
  26.  
  27.         for (int d : {-1, 1}) {
  28.             int v = u + d;
  29.             if (v < 0 || v >= N) continue;
  30.  
  31.             // 한쪽 도움
  32.             ll x = t + T[v] / 2;
  33.             if (x < c[v]) {
  34.                 c[v] = x;
  35.                 q.push({x, v});
  36.             }
  37.  
  38.             // 양쪽 도움
  39.             int other = v + (d == 1 ? 1 : -1);
  40.             if (other >= 0 && other < N && c[other] < INF) {
  41.                 x = max(t, c[other]) + T[v] / 4;
  42.                 if (x < c[v]) {
  43.                     c[v] = x;
  44.                     q.push({x, v});
  45.                 }
  46.             }
  47.         }
  48.     }
  49.  
  50.     cout << *max_element(c.begin(), c.end()) << "\n";
  51. }
Success #stdin #stdout 0.01s 5332KB
comments (?)
stdin
copy 
3
1 8 20
stdout
copy 
15
https://ideone.com/mlR1KF
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!