Submission #1347380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1347380		wyn	Ducks And Buttons (NOI25_duckbuttons)	C++17	100 / 100	44 ms	5048 KiB

Main

#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( 1 ){
            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;
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 5 / 5
• Subtask 3: 11 / 11
• Subtask 4: 6 / 6
• Subtask 5: 19 / 19
• Subtask 6: 12 / 12
• Subtask 7: 16 / 16
• Subtask 8: 23 / 23