| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 165421 |
2019-11-27T07:54:09 Z |
egekabas |
Vudu (COCI15_vudu) |
C++14 |
|
1000 ms |
19676 KB |
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<ll, ll> pii;
typedef pair<ld, ld> pld;
ll n, p;
ll ans = 0;
ll a[1000009];
vector<pll> v1;
vector<pll> v2;
ll sfunc(pll a, pll b){
return ((ld)a.ff)/((ld)a.ss) > ((ld)b.ff)/((ld)b.ss);
}
void calc(ll l, ll r){
if(l == r){
if(a[l] >= p)
++ans;
return;
}
ll m = (l+r)/2;
calc(l, m);
calc(m+1, r);
ll sum = 0;
ll cnt = 0;
v1.clear();
v2.clear();
for(ll i = m; i >= l; --i){
sum += a[i];
cnt++;
v1.pb({sum, cnt});
}
sum = 0, cnt = 0;
for(ll i = m+1; i <= r; ++i){
sum += a[i];
cnt++;
v2.pb({sum, cnt});
}
sort(v1.begin(), v1.end(), sfunc);
sort(v2.begin(), v2.end(), sfunc);
int j = v2.size()-1;
for(int i = 0; i < v1.size(); ++i){
for(j; j >= 0; --j)
if(v1[i].ff+v2[j].ff >= p*(v1[i].ss+v2[j].ss))
break;
ans += j+1;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
cin >> n;
for(ll i = 0; i < n; ++i){
cin >> a[i];
}
cin >> p;
calc(0, n-1);
cout << ans << "\n";
}
Compilation message
vudu.cpp: In function 'void calc(ll, ll)':
vudu.cpp:50:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < v1.size(); ++i){
~~^~~~~~~~~~~
vudu.cpp:51:14: warning: statement has no effect [-Wunused-value]
for(j; j >= 0; --j)
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
632 KB |
Output isn't correct |
| 2 |
Incorrect |
10 ms |
632 KB |
Output isn't correct |
| 3 |
Incorrect |
9 ms |
632 KB |
Output isn't correct |
| 4 |
Execution timed out |
1074 ms |
18940 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1068 ms |
13912 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1058 ms |
16912 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1022 ms |
17556 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1073 ms |
18768 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1057 ms |
19676 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1067 ms |
16988 KB |
Time limit exceeded |
