Submission #4037574
Source Code Expand
#include <bits/stdc++.h> using namespace std; using ll = long long; #define FOR(i, a, b) for(int i=(a);i<(b);++i) #define FORE(i, a, b) for(int i=(a);i<=(b);++i) #define rep(i, n) for(int i=0;i<(n);++i) #define repe(i, n) for(int i=0;i<=(n);++i) #define ALL(v) (v).begin(),(v).end() #define SP cout<<fixed<<setprecision(10) typedef pair<int, int> P; const int inf = (int) 1e9; const int mod = (int) 1e9 + 7; template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; } int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; int main(void) { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; ll a[n]; int pos[n]; rep(i, n) { cin >> a[i]; pos[a[i] - 1] = i; } set<int> st; st.insert(-1); st.insert(n); ll sum = 0; rep(i, n) { auto iter = st.lower_bound(pos[i]); ll right = (*iter) - pos[i]; iter--; ll left = pos[i] - (*iter); sum += a[pos[i]] * left * right; st.insert(pos[i]); } cout << sum << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - Minimum Sum |
User | sdub |
Language | C++14 (GCC 5.4.1) |
Score | 400 |
Code Size | 1232 Byte |
Status | AC |
Exec Time | 117 ms |
Memory | 12032 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 | 93 ms | 12032 KB |
corner1 | AC | 91 ms | 12032 KB |
corner2 | AC | 1 ms | 256 KB |
corner3 | AC | 71 ms | 12032 KB |
example0 | AC | 1 ms | 256 KB |
example1 | AC | 1 ms | 256 KB |
example2 | AC | 1 ms | 256 KB |
maxrand0 | AC | 117 ms | 12032 KB |
maxrand1 | AC | 117 ms | 12032 KB |
maxrand2 | AC | 113 ms | 12032 KB |
rand0 | AC | 1 ms | 256 KB |
rand1 | AC | 1 ms | 256 KB |
rand2 | AC | 1 ms | 256 KB |