oj.uz

답안 #649458

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
649458 2022-10-10T08:49:30 Z ymm Baloni (COCI15_baloni) C++17
100 / 100
 750 ms 92432 KB 
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 1'000'010;
set<int> balloons[N];
int n;

void shoot(int h)
{
	int lst = -1;
	while (h >= 0) {
		auto it = balloons[h].upper_bound(lst);
		if (it == balloons[h].end())
			break;
		lst = *it;
		balloons[h].erase(it);
		--h;
	}
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n;
	Loop (i,0,n) {
		int h;
		cin >> h;
		balloons[h].insert(i);
	}
	int ans = 0;
	LoopR (i,0,N) {
		while (balloons[i].size()) {
			shoot(i);
			++ans;
		}
	}
	cout << ans << '\n';
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 47316 KB Output is correct
2 Correct 27 ms 47280 KB Output is correct
3 Correct 26 ms 47452 KB Output is correct
4 Correct 28 ms 47476 KB Output is correct
5 Correct 592 ms 88072 KB Output is correct
6 Correct 750 ms 92432 KB Output is correct
7 Correct 651 ms 84500 KB Output is correct
8 Correct 618 ms 83996 KB Output is correct
9 Correct 536 ms 86272 KB Output is correct
10 Correct 672 ms 87660 KB Output is correct