Cod sursa(job #984322)

Utilizator danlexDan Alexandru danlex Data 14 august 2013 01:31:18
Problema Secventa 2 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#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;
}