pD
unknown
c_cpp
a year ago
2.3 kB
18
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