ABC102 D Equal Cut とりあえず真ん中を固定してみる
ABC102 D Equal Cut
問題概要
リンク参照
考察
- 真ん中を固定してみたくなります(典型っぽい)
- PとQ,RとSについては同じくらいの値になっていれば良さそうに感じます(まぁ分からんでもない)
- 同じくらいの値になる境界を探す処理が必要になります→これは累積和を取って尺取りor二分探索すれば良さそう
- 実装します
- とてもバグります(´;ω;`)ウッ…
- 非常に🌲びしい
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include<cctype> #include<utility> #include<string> #include<cmath> #include<cstring> #include<queue> #include<map> #include<set> #define REP(i, n) for(int i = 0;i < n;i++) #define REPR(i, n) for(int i = n;i >= 0;i--) #define FOR(i, m, n) for(int i = m;i < n;i++) #define FORR(i, m, n) for(int i = m;i >= n;i--) #define SORT(v, n) sort(v, v+n); #define VSORT(v) sort(v.begin(), v.end()); #define llong long long #define pb(a) push_back(a) using namespace std; typedef long long int ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template<typename T, typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...)); } template<typename T, typename V> typename enable_if<is_class<T>::value == 0>::type fill_v(T& t, const V& v) { t = v; } template<typename T, typename V> typename enable_if<is_class<T>::value != 0>::type fill_v(T& t, const V& v) { for (auto& e : t) fill_v(e, v); } #define ARRAY_MAX 100005 const ll INF = 1e9; const ll MOD = 1e9 + 7; int dx[4] = { 1,0,0,-1 }; int dy[4] = { 0,1,-1,0 }; /******************************************************************************************/ ll sum[200005]; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } for (int i = 1; i <= n; i++) { sum[i] = sum[i - 1] + a[i - 1]; } ll ans = 1LL << 60; int left = 1, center = 2,right = 3; while(center < n - 1) { while (left < center) { if (abs(sum[left] - (sum[center] - sum[left])) > abs(sum[left + 1] - (sum[center] - sum[left + 1]))) { left++; } else { break; } } while (right < n) { if (abs(sum[n] - sum[right] - (sum[right] - sum[center])) > abs(sum[n] - sum[right + 1] - (sum[right + 1] - sum[center]))) { right++; } else { break; } } ll mini = min(min(sum[left], sum[center] - sum[left]), min(sum[right] - sum[center], sum[n] - sum[right])); ll maxi = max(max(sum[left], sum[center] - sum[left]), max(sum[right] - sum[center], sum[n] - sum[right])); ans = min(ans, maxi - mini); center++; } cout << ans << endl; return 0; }