Submission #1202665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202665		pera	Fancy Fence (CEOI20_fancyfence)	C++20	12 / 100	0 ms	328 KiB

fancyfence

#include<bits/stdc++.h>
using namespace std;
int main(){
   cin.tie(0)->sync_with_stdio(0);
   int n;
   cin >> n;
   vector<long long> h(n + 1);
   for(int i = 1;i <= n;i ++){
      cin >> h[i];
   }
   vector<long long> w(n + 1);
   for(int i = 1;i <= n;i ++){
      cin >> w[i];
   }
   vector<int> L(n + 1);
   for(int i = 1;i <= n;i ++){
      L[i] = i - 1;
      while(L[i] > 0 && h[i] < h[L[i]]){
         L[i] = L[L[i]];
      }
   }
   vector<int> R(n + 1);
   for(int i = n;i >= 1;i --){
      R[i] = i + 1;
      while(R[i] <= n && h[i] <= h[R[i]]){
         R[i] = R[R[i]];
      }
   }
   long long ans = 0;
   vector<long long> sum(n + 1);
   for(int i = 1;i <= n;i ++){
      sum[i] = sum[i - 1] + w[i];
   }
   for(int i = 1;i <= n;i ++){
      ans += w[i] * (w[i] + 1) * h[i] * (h[i] + 1) / 4; 
      ans += ((sum[i] - sum[L[i]]) * (sum[R[i] - 1] - sum[i - 1]) - 1LL * w[i] * w[i]) * h[i] * (h[i] + 1) / 2;
   }
   cout << ans << '\n';
}

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 18
• Subtask 7: 0 / 27