Submission #905789
Source Code Expand
#include <bits/stdc++.h> using namespace std; int a[200100], l[200100], r[200100]; stack < pair<int, int> > ll, rr; int main(){ int i, N; cin>>N; for(i=1; i<=N; i++) cin>>a[i]; a[0] = 0; a[N+1] = 0; for(i=1; i<=N+1; i++){ while(ll.size() > 0){ if(ll.top().first > a[i]){ r[ll.top().first] = i - ll.top().second-1; ll.pop(); }else{ break; } } ll.push(make_pair(a[i], i)); } for(i=N; i>=0; i--){ while(rr.size() > 0){ if(rr.top().first > a[i]){ l[rr.top().first] = rr.top().second-i-1; rr.pop(); }else{ break; } } rr.push(make_pair(a[i], i)); } long long cnt=0; for(i=1; i<=N; i++){ long long K = l[i] + r[i] + 1; K *= (K+1); K /= 2; K-=( (l[i] * (l[i]+1) / 2 ) ) + ( (r[i] * (r[i]+1) / 2 ) ); cnt+=K*i; } printf("%lld", cnt); }
Submission Info
Submission Time | |
---|---|
Task | B - Minimum Sum |
User | tae826 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1077 Byte |
Status | WA |
Exec Time | 72 ms |
Memory | 3640 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 400 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | example0, example1, example2 |
All | corner0, corner1, corner2, corner3, example0, example1, example2, maxrand0, maxrand1, maxrand2, rand0, rand1, rand2 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
corner0 | WA | 70 ms | 3640 KB |
corner1 | WA | 70 ms | 3640 KB |
corner2 | AC | 3 ms | 256 KB |
corner3 | WA | 70 ms | 3252 KB |
example0 | AC | 3 ms | 256 KB |
example1 | AC | 3 ms | 256 KB |
example2 | AC | 3 ms | 256 KB |
maxrand0 | WA | 72 ms | 2560 KB |
maxrand1 | WA | 72 ms | 2560 KB |
maxrand2 | WA | 72 ms | 2560 KB |
rand0 | AC | 3 ms | 256 KB |
rand1 | AC | 3 ms | 256 KB |
rand2 | AC | 3 ms | 256 KB |