2019-05-08 23:47:12 C++

C++

Copy Copied! Full
#include <bits/stdc++.h> using namespace std; long long b[100005]; int main(void){ int N,Q,flag; int right=0; cin >> N >> Q; long long a[N+1]; long long x[Q]; for(int i=1;i<=N;i++)cin >> a[i]; for(int i=0;i<Q;i++)cin >> x[i]; b[0]=0; for(int i=1;i<=N;i++)b[i]=b[i-1]+a[i]; //(l,r)はb[r]-b[l-1]で出せる //各x[i]について for(int i=0;i<Q;i++){ //( l,r)が満たされていたらl,l+1,l+2...l+?=rまで成り立つはず //あるlに対して一番大きいrを求める long long ans = 0; flag = 0; for(int left=1;left<=N;left++){ if(flag==0){ for(right=N;right>=left;right--){ if(x[i]>=b[right]-b[left-1]){ //rightはあるleftに対して一番大きいrightである //これを保持しておいて、left++したらrightはここから右にいけるか //どうかを調べれば良いのであ~る ans += right-(left-1); flag = 1; break; } } }else{ //上の分岐でrightが見つかった場合に以下を実行する //leftは既に加算済みなので、rightを増やせるかどうか調べる int j=0; while(x[i]>=(b[right+j]-b[left-1])&&(right+j)<N){ j++; if(x[i]<(b[right+j]-b[left-1])){ j--; break; } } right = right+j; ans += right-(left-1); } } cout << ans << endl; } }
RECOMMEND