Pagini recente » Cod sursa (job #1987344) | Cod sursa (job #88533) | Monitorul de evaluare | Cod sursa (job #2047747) | Cod sursa (job #1186084)
#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++)
{
if(i >= t) stanga(i);
dreapta(i);
sum += (long long)c[coada[st]] * p[i] + (long long)s * (i - coada[st]) * p[i];
}
out<<sum<<'\n';
return 0;
}