pD

 avatar
unknown
c_cpp
5 months ago
2.3 kB
6
Indexable
#include <iostream>
#include <vector>
#include <climits>
#define ll long long

using namespace std;

// Function to calculate the value of V^2 + D^2
ll calculateValue(ll V, ll D) {
    return V * V + D * D;
}

// Main function to find the best pair using divide and conquer
pair<int, int> findBestPair(vector<int>& a, int left, int right, vector<ll>& prefix) {
    if (left == right) {
        return {-1, -1};  // no valid pair in a single element
    }

    int mid = (left + right) / 2;
    pair<int, int> bestLeft = findBestPair(a, left, mid, prefix);
    pair<int, int> bestRight = findBestPair(a, mid + 1, right, prefix);

    ll bestValue = LLONG_MAX;
    pair<int, int> bestPair = {-1, -1};

    // Compare pairs in left and right subarrays
    if (bestLeft.first != -1) {
        int x = bestLeft.first, y = bestLeft.second;
        ll V = prefix[y] - prefix[x - 1];
        ll D = y - x + 1;
        ll value = calculateValue(V, D);
        if (value < bestValue) {
            bestValue = value;
            bestPair = {x, y};
        }
    }

    if (bestRight.first != -1) {
        int x = bestRight.first, y = bestRight.second;
        ll V = prefix[y] - prefix[x - 1];
        ll D = y - x + 1;
        ll value = calculateValue(V, D);
        if (value < bestValue) {
            bestValue = value;
            bestPair = {x, y};
        }
    }

    // Check across the midpoint
    for (int i = mid; i >= left; --i) {
        for (int j = mid + 1; j <= right; ++j) {
            ll V = prefix[j] - prefix[i - 1];
            ll D = j - i + 1;
            ll value = calculateValue(V, D);
            if (value < bestValue) {
                bestValue = value;
                bestPair = {i, j};
            }
        }
    }

    return bestPair;
}

int main() {
    int N;
    cin >> N;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }

    // Prefix sum array
    vector<ll> prefix(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        prefix[i] = prefix[i - 1] + a[i - 1];
    }

    pair<int, int> result = findBestPair(a, 1, N, prefix);
    cout << result.first << " " << result.second << endl;

    return 0;
}
Editor is loading...
Leave a Comment