Pagini recente » Cod sursa (job #621427) | Cod sursa (job #2417916) | Cod sursa (job #1196038) | Cod sursa (job #2291002) | Cod sursa (job #2063827)
#include <fstream>
using namespace std;
ifstream in("branza.in");
ofstream out("branza.out");
int v[100000],d[100000],C[100000];
int main()
{
long long sum=0,s;
int st=0,dr=-1,n,k;
in>>n>>s>>k;
k++;
for(int i=0; i<n; i++)
{
in>>C[i]>>v[i];
if(st<=dr && d[st]==i-k)
{
st++;
}
while(st<=dr && C[i] <= C[d[dr]] + s*(i - d[dr]))
{
dr--;
}
d[++dr] = i;
//out << d[st] << " " << C[d[st]] << "\n";
sum += v[i]*(C[d[st]] + (long long)s*(i-d[st]));
}
out<<sum;
return 0;
}