Submission #462600

#TimeUsernameProblemLanguageResultExecution timeMemory
462600Hamed5001Vudu (COCI15_vudu)C++14
42 / 140
1093 ms18016 KiB
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

void solve() {
	int N, P;
	cin >> N;
	vector<int> A(N); for (auto& a : A) cin >> a;
	cin >> P;
	for (auto& a : A) a-=P;

	vector<int> AA;

	int sum = 0;
	for (auto a : A) {
		sum += a;
		AA.push_back(sum);
	}

	sort(AA.begin(), AA.end());

	sum = 0;
	ll ans = 0;
	for (auto a : A) {
		auto it = lower_bound(AA.begin(), AA.end(), sum);

		if (it != AA.end()) {
			ll add = AA.size() - (it - AA.begin());
			ans += add;
		}
		sum += a;
		AA.erase(lower_bound(AA.begin(), AA.end(), sum));
	}

	cout << ans;
}

int main() {
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...