Submission #1591052
Source Code Expand
#include <bits/stdc++.h> #define rep(i, a, n) for(int i = a; i < n; i++) #define REP(i, n) rep(i, 0, n) #define repb(i, a, b) for(int i = a; i >= b; i--) #define all(a) a.begin(), a.end() #define int long long #define chmax(x, y) x = max(x, y) #define chmin(x, y) x = min(x, y) using namespace std; typedef pair<int, int> P; const int mod = 1000000007; const int INF = 1e12; signed main(){ ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<P> d; for(int i = 0; i < n; i++){ int a; cin >> a; d. push_back((P(a, i))); } sort(all(d)); int ans = 0; set<int> st; st.insert(-1); st.insert(n); rep(i, 0, n){ st.insert(d[i].second); auto it = st.find(d[i].second); it++; int right = *it; it--; it--; int left = *it; int tmp = (right - d[i].second) * (d[i].second - left); ans += tmp * d[i].first; // cout << right << ' ' << left << ' ' << tmp << endl; } cout << ans << endl; }
Submission Info
Submission Time | |
---|---|
Task | B - Minimum Sum |
User | treeone |
Language | C++14 (GCC 5.4.1) |
Score | 400 |
Code Size | 1072 Byte |
Status | AC |
Exec Time | 125 ms |
Memory | 13676 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 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 | AC | 122 ms | 13164 KB |
corner1 | AC | 125 ms | 12780 KB |
corner2 | AC | 1 ms | 256 KB |
corner3 | AC | 89 ms | 12780 KB |
example0 | AC | 1 ms | 256 KB |
example1 | AC | 1 ms | 256 KB |
example2 | AC | 1 ms | 256 KB |
maxrand0 | AC | 123 ms | 13676 KB |
maxrand1 | AC | 122 ms | 12780 KB |
maxrand2 | AC | 122 ms | 12908 KB |
rand0 | AC | 1 ms | 256 KB |
rand1 | AC | 1 ms | 256 KB |
rand2 | AC | 1 ms | 256 KB |