제출 #1099642

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1099642		venoman	Baloni (COCI15_baloni)	C++17	100 / 100	47 ms	11960 KiB

baloni

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    int niz[n];
    int maxH = 0;
    for(int i = 0; i < n; i++){
        cin >> niz[i];
        maxH = max(maxH, niz[i]);
    }
    int brojac = 0;
    int baloni = 0;
    vector< vector<int> > a(maxH+1);
    for(int i = 0; i < n; i++) a[niz[i]].push_back(i);
    while(baloni < n){
        while(a[maxH].size() == 0) maxH--;
        int trenutnaVisina = maxH;
        int trenutnaPozicija = a[trenutnaVisina].back();
        while(trenutnaVisina >0){
            if(a[trenutnaVisina-1].size() != 0  && a[trenutnaVisina-1].back() >= trenutnaPozicija){
                baloni++;
                trenutnaPozicija = a[trenutnaVisina-1].back();
                a[trenutnaVisina].pop_back();
                trenutnaVisina--;
            }
            else
            {
                baloni++;
                a[trenutnaVisina].pop_back();
                trenutnaVisina--;
                break;
            }
        }
        brojac++;
    }
    cout<<brojac;
}

• Subtask 1: 100 / 100