pD
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