제출 #165421

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
165421		egekabas	Vudu (COCI15_vudu)	C++14	0 / 140	1074 ms	19676 KiB

vudu

#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";
}

컴파일 시 표준 에러 (stderr) 메시지

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)
              ^

• Subtask 1: 0 / 140