Submission #1632286


Source Code Expand

Copy
#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
#include <utility>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector<pair<int,int> > A;
  int a;
  for(int i = 0; i < N; ++i){
    cin >> a;
    A.push_back(make_pair(a,i));
  }
  sort(A.begin(),A.end());
  set<int> s;
  s.insert(-1);
  s.insert(N);
  long long int ans = 0LL;
  for(int i = 0; i < N; ++i){
    int id = A[i].second;
    set<int>::iterator u = upper_bound(s.begin(),s.end(),id), l = u;
    --l;
    ans += (long long int)(*u - id)*(id - (*l))*A[i].first;
    s.insert(id);
  }
  cout << ans << endl;
  return 0;
}

Submission Info

Submission Time
Task B - Minimum Sum
User TAB
Language C++14 (GCC 5.4.1)
Score 0
Code Size 647 Byte
Status

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 example0, example1, example2
All 0 / 400 corner0, corner1, corner2, corner3, example0, example1, example2, maxrand0, maxrand1, maxrand2, rand0, rand1, rand2
Case Name Status Exec Time Memory
corner0
corner1
corner2 1 ms 256 KB
corner3
example0 1 ms 256 KB
example1 1 ms 256 KB
example2 1 ms 256 KB
maxrand0
maxrand1
maxrand2
rand0 2 ms 256 KB
rand1 1 ms 256 KB
rand2 1 ms 256 KB