Pagini recente » Cod sursa (job #941894) | Cod sursa (job #1655041) | Cod sursa (job #1406802) | Cod sursa (job #3146948) | Cod sursa (job #409661)
Cod sursa(job #409661)
# include <fstream>
# include <iostream>
using namespace std;
struct branza{
long long int p, c;};
long long int n, s, t;
long long int sol;
branza v[100003];
void read ()
{
ifstream fin ("branza.in");
fin>>n>>s>>t;
for (int i=1;i<=n;i++)
fin>>v[i].c>>v[i].p;
}
void solve ()
{
branza dq[100003];
int st, dr;
st=dr=1;
dq[st].c=v[1].c;
dq[st].p=1;
for (int i=1;i<=n;i++)
{
if (v[i].c*v[i].p<=dq[st].c*v[i].p+(i-dq[st].p)*s*v[i].p)
sol+=v[i].c*v[i].p;
else
sol+=dq[st].c*v[i].p+(i-dq[st].p)*s*v[i].p;
if (i-dq[st].p==t)
st++;
while (st<=dr && v[i].c<=dq[dr].c+s)--dr;
dq[++dr].c=v[i].c;
dq[dr].p=i;
}
}
int main()
{
read();
solve ();
ofstream fout ("branza.out");
fout<<sol;
return 0;
}