Submission #46991

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
#include<complex>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<cstring>
#include<cassert>
using namespace std;

#define REP(i,x,n) for(int i = x ; i < (int)(n) ; i++)
#define rep(i,n) REP(i, 0, n)
#define f first
#define s second
#define mp make_pair
#define pb push_back

typedef pair<int,int> P;
typedef long long ll;

static const int INF = (1<<29);
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

int n;
int d[500];
int sum[500];

int main(){
  cin >> n;
  rep(i,n) cin >> d[i];
  int maxi = 0;
  int mini = INF;
  
  // maxi
  rep(i,n) maxi += d[i];
  
  //mini
  if(n==1){
    mini = d[0];
  }
  else if(n==2){
    mini = abs(d[0] - d[1]);
  }
  else{
    rep(i,n) REP(j,i,n) sum[j] += d[i];
    for(int i = 0; i < n - 1; i++){
      if(mini == 0) break;
      for(int j = i + 1; j < n - 1; j++){
        int a[3];
        a[0] = sum[i];
        a[1] = sum[j] - sum[i];
        a[2] = sum[n-1] - sum[j];
        sort(a,a+3);
        if(a[0] + a[1] >= a[2] && a[1] + a[2] >= a[0] && a[2] + a[0] >= a[1]){
          mini = 0;
          break;
        }
        else mini = min(mini, a[2] - a[1] - a[0]);
      }
    }
  }
  cout << maxi << endl;
  cout << mini << endl;
  return 0;
}

Submission Info

Judge Result