Pagini recente » Cod sursa (job #2204550) | Cod sursa (job #3170250) | Cod sursa (job #1888548) | Cod sursa (job #1435050) | Cod sursa (job #1186041)
#include <fstream>
using namespace std;
ifstream in("branza.in");
ofstream out("branza.out");
int s , t , c[100001] , p[100001] , coada[100001] , st , dr;
inline void stanga(int i)
{
if(i - t == coada[st])
st--;
}
inline void dreapta(int i)
{
while(st <= dr && c[i] <= c[coada[dr]] + s * (i - coada[dr]))
dr--;
coada[++dr] = i;
}
int main()
{
int n , i;
long long sum;
in>>n>>s>>t;
for(i = 1 ; i <= n ; i++)
in>>c[i]>>p[i];
st = 1;
dr = 0;
sum = 0;
for(i = 1 ; i <= n ; i++)
{
dreapta(i);
stanga(i);
sum += c[coada[st]] * p[i] + s * (i - coada[st]) * p[i];
}
out<<sum<<'\n';
return 0;
}