oj.uz

Submission #1099642

# Submission time Handle Problem Language Result Execution time Memory
1099642 2024-10-11T22:20:52 Z venoman Baloni (COCI15_baloni) C++17
100 / 100
 47 ms 11960 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 47 ms 11840 KB Output is correct
6 Correct 45 ms 11960 KB Output is correct
7 Correct 45 ms 11344 KB Output is correct
8 Correct 40 ms 9808 KB Output is correct
9 Correct 42 ms 11856 KB Output is correct
10 Correct 41 ms 11092 KB Output is correct