Submission #103614

#	Time	Username	Problem	Language	Result	Execution time	Memory
103614		leonarda	Baloni (COCI15_baloni)	C++14	0 / 100	2071 ms	93424 KiB

baloni

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int, int> pi;
typedef long long int lint;
const int inf = 0x3f3f3f3f;
const int maxn = 1e6 + 5;

int n, ans;
set<int> v[maxn];
int a[maxn];
bool memo[maxn];

int main ()
{
	ios::sync_with_stdio(0);
	
	cin >> n;
	for(int i = 0; i < n; ++i) {
		cin >> a[i];
		v[a[i]].insert(i);
	}
	
	for(int i = 0; i < n; ++i) {
		
//		cout << "i " << i << endl;
		
		if(!memo[i]) {
			memo[i] = 1;
			
			int indeks = i + 1;
			int h = a[i];
			--h;
			
			for(int j = a[i] - 1; j >= 0; --j) {
				bool ok = 0;
				for(set<int>::iterator it = v[j].begin(); it != v[j].end(); ++it) {
					if(*it >= indeks and a[*it] == h) {
						memo[*it] = 1;
						indeks = *it + 1;
						--h;
						ok = 1;
						continue;
//						break;
					}
				}
				if(!ok) break;
			}
			++ans;
		}
		
	}
	
	cout << ans;

return 0;
}

• Subtask 1: 0 / 100