Cod sursa(job #1707134)
Utilizator | Vasiesiu Victor Victor24 | Data | 24 mai 2016 12:01:06 |
---|---|---|---|
Problema | Deque | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 2.08 kb |
#include <fstream>
using namespace std;
ifstream f ("deque.in");
ofstream g ("deque.out");
int dq[10000005], st, dr, i, a[5000005], n, k, ver, j, k1;
long long s;
int main ()
{
f>>n>>k;
st=dr=5000000;
dq[dr]=1;
st--;
dr++;
f>>a[1];
for (i=2; i<=k; i++)
{
f>>a[i];
if( a[i] >= a[ dq[ dr-1 ] ] )
{
dq[dr]=i;
dr++;
}
else
{
for (j=dr-1; j>st; j-- )
{
if ( a[ dq [ j ] ] < a[i] )
{
ver=j+1;
break;
}
}
if (j==st)
{
ver=st+1;
}
//cout<<"POZITIA "<<ver-5000000<<'\n';
dq[ver]=i;
dr=ver+1;
}
}
//cout<<st<<" "<<dr<<'\n';
/*cout<<st-5000000<<" "<<dr-5000000<<'\n';
for(k1=st; k1<=dr; k1++)
{
cout<<dq[k1]<<" ";
}
cout<<'\n';*/
//cout<<a[ dq [ st+1 ] ]<<'\n';
s+=a[ dq [ st+1 ] ];
for (i=k+1; i<=n; i++)
{
f>>a[i];
if( a[i] >= a[ dq[ dr-1 ] ] )
{
dq[dr]=i;
dr++;
}
else
{
for (j=dr-1; j>st; j-- )
{
if ( a[ dq [ j ] ] < a[j] )
{
ver=i+1;
break;
}
}
if (j==st)
{
ver=st+1;
}
// cout<<"POZITIA "<<ver-5000000<<'\n';
dq[ver]=i;
dr=ver+1;
}
if ( dq [ st + 1 ] < i - k +1 )
{
st++;
}
s+=a[ dq [ st+1 ] ];
//cout<<a[ dq [ st+1 ] ]<<'\n';
/*cout<<st-5000000<<" "<<dr-5000000<<'\n';
for(k1=st; k1<=dr; k1++)
{
cout<<dq[k1]<<" ";
}
cout<<'\n';*/
}
g<<s;
return 0;
}