제출 #1191334

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191334		oguzhan09	Mountains (NOI20_mountains)	C++20	70 / 100	2094 ms	7372 KiB

Mountains

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<ll>l(n);
    ll enb=0;
    ll say=0;
    for(int i=0;i<n;i++){
        cin>>l[i];
        enb=max(enb,l[i]);
    }
    if(is_sorted(l.begin(),l.end())){
        cout<<0<<endl;
        return 0;
    }
    if(enb==1){
        bool seen=false;
        ll pref[n];
        ll suf[n];
        pref[0]=0;
        if(l[0]==0) pref[0]++;
        for(int i=1;i<n;i++){
            pref[i]=pref[i-1];
            if(l[i]==0) pref[i]++;

        }
       /* for(int x:pref) cout<<x<<" ";
        cout<<endl;*/
        suf[n-1]=0;
        if(l[n-1]==0) suf[n-1]++;
        for(int i=n-2;i>=0;i--){
            suf[i]=suf[i+1];
            if(l[i]==0) suf[i]++;
        }
        /*for(int x:suf){
            cout<<x<<" ";
        }
        cout<<endl;*/

        for(int i=0;i<n;i++){
            if(l[i]==1){
                say+=suf[i]*pref[i];
            }
        }

        cout<<say<<endl;
        return 0;
    }

    for(int i=1;i<n-1;i++){
        ll sol_say=0,sag_say=0;
        for(int j=0;j<i;j++){
            if(l[j]<l[i]) sol_say++;
        }
        for(int j=i+1;j<n;j++){
            if(l[j]<l[i]) sag_say++;
        }

        say+=sol_say*sag_say;
    }

    cout<<say<<endl;

}

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 0 / 9
• Subtask 4: 36 / 36
• Subtask 5: 28 / 28
• Subtask 6: 0 / 9
• Subtask 7: 0 / 12