UVa12697 Minimum Subarray Length

まだ考え中。現時点で二回練習に出ている。

続きを読むをすると、多くの人が書く正答コードが見られる。

#include <bits/stdc++.h>

using namespace std;

#define allof(c) (c).begin(), (c).end()

typedef long long ll;

int const INF = 1<<29;

int main() {

  int Tc; cin >> Tc;
  while(Tc--) {
    int N, X; cin >> N >> X;
    
    ll sum = 0;
    vector<pair<ll, int> > vec;
    for(int i=0; i<N; i++) {
      int a; cin >> a;
      sum += a;
      vec.push_back(make_pair(sum, i+1));
    }
    
    sort(allof(vec));
    
    int ans = INF;
    set<int> st;
    for(int low=N-1, high=N-1; low>=0; --low) {
      while(high >= 0 && vec[low].first+X <= vec[high].first) {
	st.insert(vec[high--].second);
      }
      set<int>::iterator it = st.upper_bound(vec[low].second);
      if(it != st.end()) {
	ans = min(ans, *it - vec[low].second);
      }
    }
    cout << (ans == INF ? -1 : ans) << endl;
  }
  
  return 0;
}