fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. void solve() {
  8.     int t;
  9.     if (!(cin >> t)) return;
  10.     while (t--) {
  11.         int n;
  12.         cin >> n;
  13.         vector<long long> h(n);
  14.         for (int i = 0; i < n; ++i) {
  15.             cin >> h[i];
  16.         }
  17.         vector<long long> R(n), L(n);
  18.         for (int k = 0; k < n; ++k) {
  19.             R[k] = 0;
  20.             for (int step = 1; step < n; ++step) {
  21.                 int curr = (k + step) % n;
  22.                 int prev = (curr - 1 + n) % n;
  23.                 R[curr] = max(R[prev], h[prev]);
  24.             }
  25.             L[k] = 0;
  26.             for (int step = 1; step < n; ++step) {
  27.                 int curr = (k - step + n) % n;
  28.                 int next = (curr + 1) % n;
  29.                 L[curr] = max(L[next], h[curr]);
  30.             }
  31.             long long sum = 0;
  32.             for (int i = 0; i < n; ++i) {
  33.                 sum += min(L[i], R[i]);
  34.             }
  35.             cout << sum << (k == n - 1 ? "" : " ");
  36.         }
  37.         cout << "\n";
  38.     }
  39. }
  40.  
  41. int main() {
  42.     ios_base::sync_with_stdio(false);
  43.     cin.tie(NULL);
  44.     solve();
  45.     return 0;
  46. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
4
4
1 2 3 4
5
5 3 1 5 2
6
3 4 2 6 1 5
7
1 2 1 4 2 3 5
stdout 
6 6 7 9
17 16 14 14 17
21 21 20 20 21 21
17 17 17 17 21 21 22
https://ideone.com/vbbDDs
language:
C++14 (gcc 8.3)
created:
1 day 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!