CCC '23 S2 - Symmetric Mountains

#include <iostream> #include <vector> int main(){ long long N; std::cin >> N; std::vector<long long> mins (N + 1, 21487777886); //mins[i] tells us the minimum assymetry for crop size i, default is very big number so that when we compare min it takes the initial value std::vector<long long> mountains (N); for (int i = 0; i < N; i++){ std::cin >> mountains[i]; } //For odd numbered crop sizes for (long long mid = 0; mid < N; mid++){ long long left = mid, right = mid; long long size = 1; long long assy = 0; mins[size] = assy; //Go until out of bounds while (left > 0 && right < N - 1){ left--; right++; size += 2; assy += std::abs(mountains[left] - mountains[right]); mins[size] = std::min(assy, mins[size]); //Only change if the resulting value is lower } } long long mid1 = 0, mid2 = 1; //For even number crop sizes while(mid2 < N){ long long left = mid1, right = mid2; long long size = 2; long long assy = std::abs(mountains[mid1] - mountains[mid2]); mins[size] = std::min(assy, mins[size]); while (left > 0 && right < N - 1){ left--; right++; size += 2; assy += std::abs(mountains[left] - mountains[right]); //Add 2 new outer mountains mins[size] = std::min(assy, mins[size]); //Take min only } mid1++; mid2++; } for (int i = 1; i <= N; i++){ std::cout << mins[i] << ' '; } return 0; }