Pagini recente » Cod sursa (job #2934506) | Cod sursa (job #2842416) | Cod sursa (job #1797477) | Cod sursa (job #356102) | Cod sursa (job #1829107)
#include <fstream>
using namespace std;
ifstream in("branza.in");
ofstream out("branza.out");
long long t,v[100001],d[100001],v2[100001],st,dr=-1,k;
inline void stanga(int i)
{
if(i-k==d[st])
st++;
}
inline void dreapta(int i)
{
while(st<=dr&&v[i]<=v[d[dr]]+t*(i-d[dr]))
dr--;
d[++dr]=i;
}
void scrie()
{
for (int i = st; i <= dr; i++)
{
out << d[i] << " ";
}
out << "\n";
}
int main()
{
int n,i;
long long s=0;
in>>n>>t>>k;
for(i=1; i<=n; i++)
{
in>>v[i]>>v2[i];
dreapta(i);
if(i>=k)
{
stanga(i);
}
//scrie();
s+=v[d[st]]*v2[i]+v2[i]*t*(i-d[st]);
}
out<<s;
return 0;
}