Pagini recente » Cod sursa (job #552372) | Cod sursa (job #957355) | Cod sursa (job #2492353) | Cod sursa (job #2178937) | Cod sursa (job #984322)
Cod sursa(job #984322)
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
#define MAX 500002
int k, n, v[MAX], xmin, xmax;
deque<int> dq;
long long xsum = -1250000001, dqsum = 0, s[MAX];
void print(){
cout << endl;
cout << n << " " << k << endl;
for(int i = 1; i <= n; i ++){
cout << v[i] << " ";
}
cout << endl;
cout << xmin << " " << xmax << " " << xsum << endl;
cout << endl;
}
void read(){
ifstream fi("secv2.in");
fi>>n>>k; fi.ignore();
char *a=new char[n*7];
fi.read(a,n*7);
unsigned j=0;
for(int i=1;i<=n;i++){
int sgn=1;
if(a[j]=='-') { sgn=-1; j++;}
while(isdigit(a[j])){
v[i]=v[i]*10+a[j]-'0';
j++;
}
j++;
v[i]*=sgn;
}
fi.close();
}
void write(){
ofstream fo("secv2.out");
fo << xmin << " " << xmax << " " << xsum;
fo.close();
}
void compute(){
int ifront;
long long dqfrontsum;
for(int i = 1; i <= n; i ++){
dqfrontsum = 0;
ifront = 0;
if(!dq.empty())
for(int it = dq.front(); it < dq.back() && dq.back() - it >= k - 1; it ++){
dqfrontsum += v[it];
if(dqfrontsum <= 0) ifront = it;
}
if(ifront > 0){
while(dq.front() <= ifront){
dqsum -= v[dq.front()];
dq.pop_front();
}
}
dqsum += v[i];
dq.push_back(i);
if(dq.back() - dq.front() >= k -1 && dqsum > xsum){
xsum = dqsum;
xmin = dq.front();
xmax = dq.back();
}
}
}
int main(void){
read();
compute();
//print();
write();
return 0;
}