fork download
copy 
  1.  
  2.  
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define file "o"
  7. #define ff(i, a, b) for(auto i=(a); i<=(b); ++i)
  8. #define ffr(i, b, a) for(auto i=(b); i>=(a); --i)
  9. #define nl "\n"
  10. #define ss " "
  11. #define pb emplace_back
  12. #define fi first
  13. #define se second
  14. #define sz(s) (int)s.size()
  15. #define all(s) (s).begin(), (s).end()
  16. #define ms(a,x) memset(a, x, sizeof (a))
  17. #define cn continue
  18. #define re exit(0)
  19.  
  20. typedef long long ll;
  21. typedef unsigned long long ull;
  22. typedef long double ld;
  23. typedef vector<int> vi;
  24. typedef vector<ll> vll;
  25. typedef pair<int, int> pii;
  26. typedef pair<ll, ll> pll;
  27. typedef vector<pii> vpii;
  28. typedef vector<pll> vpll;
  29.  
  30. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  31. ll ran(ll l, ll r)
  32. {
  33.     return uniform_int_distribution<ll> (l, r)(rng);
  34. }
  35.  
  36. inline void rf()
  37. {
  38.     ios_base::sync_with_stdio(false);
  39.     cin.tie(nullptr); cout.tie(nullptr);
  40.     if(fopen(file".inp","r"))
  41.     {
  42.         freopen(file".inp","r",stdin);
  43.         freopen(file".out","w",stdout);
  44.     }
  45. }
  46.  
  47. const int mod=998244353;
  48. const int maxn=3e5+15;
  49. const ll inf=1e18;
  50.  
  51. template<typename T> inline void add(T &x, const T &y)
  52. {
  53.     x+=y;
  54.     if(x>=mod) x-=mod;
  55.     if(x<0) x+=mod;
  56. }
  57.  
  58. template<typename T> inline bool maxi(T &a, T b)
  59. {
  60.     if(a>=b) return 0;
  61.     a=b; return 1;
  62. }
  63.  
  64. template<typename T> inline bool mini(T &a, T b)
  65. {
  66.     if(a<=b) return 0;
  67.     a=b; return 1;
  68. }
  69.  
  70. int n, h[maxn], l[maxn], r[maxn];
  71.  
  72. void solve()
  73. {
  74.     cin>>n;
  75.     ff(i, 0, n-1) cin>>h[i];
  76.     ff(i, 0, n-1)
  77.     {
  78.         r[i]=0; l[i]=0;
  79.         ff(step, 1, n-1)
  80.         {
  81.             int cur=(i+step)%n, pre=(cur-1+n)%n, nxt;
  82.             r[cur]=max(r[pre], h[pre]);
  83.             cur=(i-step+n)%n, nxt=(cur+1)%n;
  84.             l[cur]=max(l[nxt], h[cur]);
  85.         }
  86.         ll sum=0;
  87.         ff(j, 0, n-1) sum+=min(l[j], r[j]);
  88.         cout<<sum<<ss;
  89.     }
  90.     cout<<nl;
  91. }
  92.  
  93. signed main()
  94. {
  95.     rf();
  96.     int tt; cin>>tt;
  97.     while(tt--) solve();
  98.     re;
  99. }
  100.  
Success #stdin #stdout 0.01s 5740KB
comments (?)
stdin
copy 
3
1
43 
6
41 35 2 14 49 24 
4
27 21 8 32
stdout
copy 
0 
188 187 133 133 145 188 
81 69 56 56
https://ideone.com/2WtFtn
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!