fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. const ll INF = (ll)4e18;
  5.  
  6. int main() {
  7.     ios::sync_with_stdio(false);
  8.     cin.tie(nullptr);
  9.     int N;
  10.     if (!(cin >> N)) return 0;
  11.     vector<ll> T(N);
  12.     for (int i = 0; i < N; ++i) cin >> T[i];
  13.  
  14.     // 초기 완료시간: 시간 0에 시작했을 때 (도움 없는 경우)
  15.     vector<ll> c(N, INF);
  16.     priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
  17.  
  18.     for (int i = 0; i < N; ++i) {
  19.         c[i] = T[i];
  20.         pq.push({c[i], i});
  21.     }
  22.  
  23.     while (!pq.empty()) {
  24.         auto [t, u] = pq.top(); pq.pop();
  25.         if (t != c[u]) continue; // outdated
  26.         // relax neighbors v = u-1, u+1
  27.         for (int dir = -1; dir <= 1; dir += 2) {
  28.             int v = u + dir;
  29.             if (v < 0 || v >= N) continue;
  30.             // 한쪽 도움 (u가 이미 천재인 경우)
  31.             ll cand1 = t + (T[v] / 2); // floor
  32.             if (cand1 < c[v]) {
  33.                 c[v] = cand1;
  34.                 pq.push({c[v], v});
  35.             }
  36.             // 양쪽 도움: v의 다른 쪽 이웃 w가 이미 알고 있는 경우
  37.             int w = v + ( (v == u) ? 0 : 0 ); // dummy, we compute w explicitly below
  38.             // other neighbor of v (not u)
  39.             int other = v + ( (u == v-1) ? 1 : -1 ); // if u == v-1 then other = v+1 else other = v-1
  40.             if (other >= 0 && other < N && c[other] < INF) {
  41.                 ll maxneigh = max(t, c[other]);
  42.                 ll cand2 = maxneigh + (T[v] / 4); // floor
  43.                 if (cand2 < c[v]) {
  44.                     c[v] = cand2;
  45.                     pq.push({c[v], v});
  46.                 }
  47.             }
  48.         }
  49.     }
  50.  
  51.     ll ans = 0;
  52.     for (int i = 0; i < N; ++i) ans = max(ans, c[i]);
  53.     cout << ans << '\n';
  54.     return 0;
  55. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
10
1 4 2 18 4 2 4 7 6 3
stdout
copy 
8
https://ideone.com/hn44Ky
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!