Submission #3247581

---

Source Code Expand

    #include <bits/stdc++.h>
    using namespace std;
    /***********************************************/
    /* Dear online judge:
     * I've read the problem, and tried to solve it.
     * Even if you don't accept my solution, you should respect my effort.
     * I hope my code compiles and gets accepted.
     *  ___  __     _______    _______      
     * |\  \|\  \  |\  ___ \  |\  ___ \     
     * \ \  \/  /|_\ \   __/| \ \   __/|    
     *  \ \   ___  \\ \  \_|/__\ \  \_|/__  
     *   \ \  \\ \  \\ \  \_|\ \\ \  \_|\ \ 
     *    \ \__\\ \__\\ \_______\\ \_______\
     *     \|__| \|__| \|_______| \|_______|
     */
    const long long mod = 1000000007;
     
    int main() {
    	ios_base::sync_with_stdio(false);
    	cin.tie(nullptr);
     
    	int N;
    	cin>>N;
    	vector<long long> a(N);
    	vector<long long> pre(N);
    	for(int i = 0;i < N;i++) cin>>a[i], pre[i] = a[i] + (i?pre[i-1]:0);
    	long long res = LLONG_MAX;
    	for(int h = 1;h < N-2;h++) {
    		long long f = pre[h];
    		long long s = pre[N-1] - pre[h];
    		int f1 = upper_bound(pre.begin(),pre.end(),(f+1)/2) - pre.begin()-1;
    		int s1 = upper_bound(pre.begin(),pre.end(),pre[h] + (s+1)/2) - pre.begin()-1;
    		for(int f2 = f1;f2 < f1 + 2;f2++) {
    			if(f2 < 0 || f2 == h) continue;
    			for(int s2 = s1;s2 < s1 + 2;s2++) {
    				if(s2 <= h || s2 >= N-1) continue;
    				long long mn = min(pre[f2],pre[h] - pre[f2]);
    				mn = min(mn,min(pre[s2]-pre[h],pre[N-1] - pre[s2]));
     
    				long long mx = max(pre[f2],pre[h] - pre[f2]);
    				mx = max(mx,max(pre[s2]-pre[h],pre[N-1] - pre[s2]));
    				
    //				cerr<<f2<<' '<<h<<' '<<s2<<": "<<mn<<' '<<mx<<'\n';
    				res = min(res,mx-mn);
    			}
    		}
    	}
    	cout<<res<<'\n';
    	return 0;
    }

Submission Info

Judge Result