Pagini recente » Cod sursa (job #2499298) | Cod sursa (job #1611174) | Cod sursa (job #726162) | Cod sursa (job #1388311) | Cod sursa (job #1500263)
#include <iostream>
#include <cstdio>
#include <cctype>
#define INF 1<<30
#define NMAX 250010
using namespace std;
const int BUFF_SIZE = 1<<15;
char Buffer[BUFF_SIZE];
int pos = BUFF_SIZE;
inline char getChar ()
{
if (pos == BUFF_SIZE){
fread (Buffer, 1, BUFF_SIZE, stdin);
pos = 0;
}
return Buffer[pos ++];
}
inline long long int get ()
{
long long int x = 0;
char c;
do{
c = getChar ();
} while (!isdigit (c));
do{
x = x * 10 + c - '0';
c = getChar ();
} while (isdigit (c));
return x;
}
long long int N,M;
long long int V[NMAX];
long long int best[NMAX];
long long int S[NMAX];
long long int modul(long long int x){
if(x>0)
return x;
return -x;
}
int main()
{
freopen("cuburi2.in","r",stdin);
freopen("cuburi2.out","w",stdout);
N=get();
M=get();
long long int i,x,y;
//S[i]=suma numerele de la v[1] pana la v[i]
S[0]=0;
for(i=1;i<=N;i++)
{
V[i]=get();
S[i]=S[i-1]+V[i];
}
while(M--){
x=get();
y=get();
best[x]=0;
for(i=x;i<=y;i++)
best[x]+=( V[i] * modul( x-i ) );
long long int min=best[x],poz=x;
for(i=x+1;i<=y;i++){
best[i] = best[i-1] - ( S[y] - S[i-1] ) + ( S[i-1] - S[x-1] );
if(best[i]<=min)
{
min=best[i];
poz=i;
}
else
{
i=y+1;
}
}
printf("%lld %lld\n",poz,min);
}
return 0;
}