Submission #1352198
Source Code Expand
#pragma region include #include <iostream> #include <iomanip> #include <stdio.h> #include <sstream> #include <algorithm> #include <cmath> #include <complex> #include <string> #include <cstring> #include <vector> #include <tuple> #include <bitset> #include <queue> #include <complex> #include <set> #include <map> #include <stack> #include <list> #include <fstream> #include <random> //#include <time.h> #include <ctime> #pragma endregion //#include ///////// #define REP(i, x, n) for(int i = x; i < n; ++i) #define rep(i,n) REP(i,0,n) ///////// #pragma region typedef typedef long long LL; typedef long double LD; typedef unsigned long long ULL; #pragma endregion //typedef ////定数 const int INF = (int)1e9; const LL MOD = (LL)1e9+7; const LL LINF = (LL)1e18; const double PI = acos(-1.0); const double EPS = 1e-9; ///////// using namespace::std; /* thx http://wk1080id.hatenablog.com/entry/2017/02/11/154313 */ void solve(){ int N; cin >> N; vector<LL> A(N),order(N+1); for(int i=0;i<N;++i){ cin >> A[i]; order[ A[i]-1 ] = i;//値がある位置を記録 } set<LL> S; S.insert(-1);//左の番兵 S.insert(N);//右の番兵、値は[0,N-1]を使用している LL ans = 0; for(LL i=0;i<N;++i){//値が小さいほうから LL pos = order[i];//i番目に小さい値の位置 set<LL>::iterator itr; itr = S.lower_bound( pos );//自分は入っていないので次に大きい位置 /* (*itr)は自分より小さい値なので範囲に入らない-1 個数+1(0個も数える) (*itr)-1 - pos + 1 */ LL R = (*itr) - pos; --itr;//位置で左側、ループ順から自分より小さい値の位置 LL L = pos - (*itr); LL temp = A[pos] * L * R; ans += temp; S.insert( pos ); } cout << ans << endl; } #pragma region main signed main(void){ std::cin.tie(0); std::ios::sync_with_stdio(false); std::cout << std::fixed;//小数を10進数表示 cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別 solve(); } #pragma endregion //main()
Submission Info
Submission Time | |
---|---|
Task | B - Minimum Sum |
User | akarin55 |
Language | C++14 (GCC 5.4.1) |
Score | 400 |
Code Size | 2118 Byte |
Status | AC |
Exec Time | 119 ms |
Memory | 12800 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 | 119 ms | 12800 KB |
corner1 | AC | 117 ms | 12800 KB |
corner2 | AC | 1 ms | 256 KB |
corner3 | AC | 71 ms | 12800 KB |
example0 | AC | 1 ms | 256 KB |
example1 | AC | 1 ms | 256 KB |
example2 | AC | 1 ms | 256 KB |
maxrand0 | AC | 108 ms | 12800 KB |
maxrand1 | AC | 109 ms | 12800 KB |
maxrand2 | AC | 116 ms | 12800 KB |
rand0 | AC | 1 ms | 256 KB |
rand1 | AC | 1 ms | 256 KB |
rand2 | AC | 1 ms | 256 KB |