Longest Affordable Shop Block
National Olympiad — National round (2017 season)
Submission name: Monopoly.cpp
Problem summary
Shop costs may be negative. Find the longest consecutive block whose total cost is at most budget M; among maximum-length blocks choose the smallest starting index.
Input
N M, then N signed costs.
Output
The maximum length and its one-based starting index.
Constraints
1 ≤ N ≤ 500,000; 1 ≤ M ≤ 10⁹; −10⁶ ≤ cost ≤ 10⁶; at least one shop is affordable.
Worked example
An independently prepared example for this explanation.
Input
15 666 101 42 -132 17 404 -13 55 222 89 11 -66 91 -9 21 4
Output
10 2
Solution analysis
- Let P[j] be the cost of the first j shops. A block after prefix i and ending at j is affordable exactly when P[i]≥P[j]−M. For each right endpoint we need the earliest earlier prefix meeting this inequality.
- Keep only strict record-high prefix sums in increasing index order, starting with P[0]=0. Every omitted prefix has an earlier prefix with at least as large a sum, which is always preferable. Record values and indices both increase, so lower_bound on the record values finds the earliest feasible prefix.
- The sample’s best block starts at 2 and contains ten shops, costing 629. Another ten-shop block starts at 6, but the earlier index wins. Negative costs mean an ordinary positive-sum sliding window would discard useful starts.
Why it works
A prefix that is not a strict record high is dominated by an earlier prefix with greater or equal value: whenever the former is feasible, the latter is feasible and gives a longer block. Therefore an optimal left endpoint is a stored record. Binary search finds the first record above the required threshold, and increasing record indices make it the earliest feasible start for that endpoint. Comparing all endpoints with the specified tie rule gives the global optimum.
Watch out. Negative values invalidate a usual two-pointer sum window. Query before adding the current prefix to enforce a nonempty block. Prefix sums require 64-bit arithmetic.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<vector>
// Algorithm: Let P[j] be the cost of the first j shops.
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
long long budget;
cin>>n>>budget;
vector<long long>recordValue(1,0);
vector<int>recordIndex(1,0);
long long prefix=0;
int bestLength=0;
int bestStart=n+1;
for(int end=1;end<=n;end++){
long long cost;
cin>>cost;
prefix+=cost;
auto it=lower_bound(recordValue.begin(),recordValue.end(),prefix-budget);
if(it!=recordValue.end()){
int previous=recordIndex[it-recordValue.begin()];
int length=end-previous;
if(length>bestLength||(length==bestLength&&previous+1<bestStart)){
bestLength=length;
bestStart=previous+1;
}
}
if(prefix>recordValue.back()){
recordValue.push_back(prefix);
recordIndex.push_back(end);
}
}
cout<<bestLength<<' '<<bestStart<<'\n';
}