oj.uz

Submission #976960

# Submission time Handle Problem Language Result Execution time Memory
976960 2024-05-07T09:45:06 Z SeenSiravit Vudu (COCI15_vudu) C++14
28 / 140
 1000 ms 16284 KB 
#include<bits/stdc++.h>
#define ll long long

using namespace std;

const int mxN = 1e6 + 5;

int n;
ll a[mxN] , b[mxN];
ll p;

int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    
    cin>> n;

    for(int i=1;i<=n;i++) cin>> a[i] , a[i] += a[i-1];

    // for(int i=1;i<=n;i++) cout<< a[i] << " ";
    // cout<< "\n";

    cin>> p;

    for(int i=1;i<=n;i++) b[i] = a[i] - p*i;
    // for(int i=1;i<=n;i++) cout<< b[i] << " ";
    // cout<< "\n\n";

    vector<ll> v;

    ll ans = 0;

    for(int i=1;i<=n;i++){
        // cout<< i << " : ";
        // for(auto val : v) cout<< val << " " ;

        int cnt = upper_bound(v.begin() , v.end() , b[i]) - v.begin();

        // cout<< "\ncnt = " << cnt << " ";

        if(a[i]-a[i-1] >= p) cnt++;

        // cout<< cnt << "\n\n";

        ans += cnt;

        v.push_back(b[i-1]);
        sort(v.begin() , v.end());
    }

    cout<< ans;

    return 0;
}

Subtask #1
28.0 / 140.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 2648 KB Time limit exceeded
2 Correct 513 ms 2584 KB Output is correct
3 Correct 596 ms 2644 KB Output is correct
4 Execution timed out 1066 ms 16180 KB Time limit exceeded
5 Execution timed out 1054 ms 11120 KB Time limit exceeded
6 Execution timed out 1043 ms 15104 KB Time limit exceeded
7 Execution timed out 1071 ms 15752 KB Time limit exceeded
8 Execution timed out 1030 ms 15556 KB Time limit exceeded
9 Execution timed out 1051 ms 16284 KB Time limit exceeded
10 Execution timed out 1046 ms 15120 KB Time limit exceeded