| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1347377 | wyn | Ducks And Buttons (NOI25_duckbuttons) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
vector<int64_t> A;
int64_t N, D;
int main(){
cin >> N >> D;
A.assign( N , 0 );
for ( auto &a : A )
cin >> a;
deque< tuple<int64_t,int64_t> > buf ;
buf.push_back( {1e18,0} );
for ( int64_t n=0 ; n<N ; n++ ){
auto a = A[n];
while( auto [h,n] = buf.back() ){
if( a >= h ){
buf.pop_back();
}
else {
break;
}
}
buf.push_back( {a, n} );
}
int64_t ans = 0;
for( int64_t i=1 ; i<buf.size() ; i++ ){
auto [h,n] = buf[i];
auto [h1,n1] = buf[i-1];
ans += h*(n-n1);
}
cout << ans << endl;
return 0;
}
