Submission #763437

#	Time	Username	Problem	Language	Result	Execution time	Memory
763437		KN200711	Money (IZhO17_money)	C++14	0 / 100	1580 ms	296 KiB

money

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

multiset<int> C;

int main() {
	int N;
	scanf("%d", &N);
	
	vector<int> arr(N);
	map<int, int> MM;
	for(int i=0;i<N;i++) {
		scanf("%d", &arr[i]);
		C.insert(arr[i]);
	}
	
	int ans = 0;
	for(int i=N-1;i>=0;i--) {
		auto p = C.lower_bound(arr[i]);
		int x = C.count(arr[i]);
		
		int k = i - 1, cnt = 1;
		while(k >= 0 && arr[k] == arr[k + 1]) {
			cnt++;
			k--;
		}
		
	//	cout<<*p<<endl;
		
		bool ed = 0;
		if(p == C.begin()) ed = 1;
		else p--;
		
		while(cnt--) C.erase(C.find(arr[i]));
		
		
		if(ed) {
			ans++;
			continue;
		}
		
		while(k >= 0 && *p == arr[k]) {
		//	cout<<k<<" "<<arr[k]<< endl;
			
			auto q = p;
			if(k != 0) q--;
			
			C.erase(p);
			if(k != 0) p = q;
			
			k--;
		//	cout<<*p<<endl;
		}
		
	//	cout<<k<<endl;
		
		i = k + 1;
		ans++;
	}
	printf("%d\n", ans);
}

Compilation message (stderr)

money.cpp: In function 'int main()':
money.cpp:20:7: warning: unused variable 'x' [-Wunused-variable]
   20 |   int x = C.count(arr[i]);
      |       ^
money.cpp:8:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
money.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |   scanf("%d", &arr[i]);
      |   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 16
• Subtask 3: 0 / 20
• Subtask 4: 0 / 55