Submission #1130078

#TimeUsernameProblemLanguageResultExecution timeMemory
1130078Roumak77Global Warming (NOI13_gw)C++17
40 / 40
196 ms16216 KiB
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("-Ofast")
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <vector>
#include <limits>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
using namespace std;

using ll = long long;

void solve(){

    ll n;
    cin >> n;

    vector<pair<ll, ll>> list_n(n, {0, 0});

    for(ll i = 0; i < n; i++){
        cin >> list_n[i].first;
        list_n[i].second = i;
    }

    if(n == 1){
        if(list_n[0].first == 0){
            cout << 0 << endl;
            return;
        }else{
            cout << 1 << endl;
            return;
        }
    }

    ll cnt = 0;
    vector<bool> island(n, false);

    ll curr_max = 0;

    sort(list_n.rbegin(), list_n.rend());


    for(ll i = 0; i < n; i++){

        ll idx = list_n[i].second;

        if(idx == 0){
            island[idx] = true;
            if(!island[idx + 1]){
                cnt++;
            }
        }else if(idx == n - 1){
            island[idx] = true;
            if(!island[idx - 1]){
                cnt++;
            }
        }else{
            island[idx] = true;

            if(island[idx + 1] == true && island[idx - 1] == true){
                cnt--;
            }else if(island[idx + 1] == false && island[idx - 1] == false){
                cnt++;
            }
        }


        if(i == n - 1){
            curr_max = max(curr_max, cnt);
        }else if(list_n[i].first != list_n[i + 1].first){
            curr_max = max(curr_max, cnt);

        }


    }

    cout << curr_max << endl;





}

bool single = true;

int main(){

    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);

    ll t = 1;
    if(!single) cin >> t;

    while(t--){
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...