TheBoomsdayProject

Aloha is a poor guy who likes riding a bike. But he is too poor to afford a bicycle.

Recently, the Boom's bike-sharing service entered his school. It only costs ${r}$ yuan for every single rent of a bicycle. From then on, Aloha could rent a bike and enjoy the speed and passion of riding.

The Boom's company has launched a promotion program named the ${Boomsday Project}$ . In this program, users can buy discount cards with several free rents and a valid period. For example, after purchasing a discount card with ${k}$ free rents and ${d}$ days of valid time, one doesn't need to pay extra fees for the following ${k}$ rents in the next ${d}$ days. Note that, no matter when the card is bought on day ${t}$ , it will always expire at the end of day ${t+d-1}$ . Also, any new discount card overrides the previous one even if it is still valid, i.e., the remaining free rents of the previous discount card are voided immediately when the new discount card is purchased.

There are ${n}$ different types of discount cards in the ${Boomsday Project}$ . A card of ${i}$ th type with $k_i$ free rents and a valid period of ${d_i}$ days costs $c_i$ yuan. One can buy any type of discount card unlimited times.

Given the rental records, Aloha wants to know the minimum money he has to pay, provided that he takes the best strategy.

The first line of input contains three integers ${n,m,r}$ $(1\leq n \leq 500, 1 \leq m \leq 10^5, 1 \leq r \leq 10^9)$ , denoting the number of discount card types, the number of rental records, and the price of a single rent.
Then follow ${n}$ lines, specifying the ${n}$ types of discount cards. The ${i}$ th line contains three integers $d_i, k_i, c_i$ $(1 \leq d_i, k_i, c_i \leq 10^9)$ , denoting the valid period, the number of free rents, and the price of a discount card of type ${i}$ .
The last ${m}$ lines describe Aloha's rental records. The ${i}$ th of them contains two integers $p_i, q_i$ $(0 \leq p_i \leq 10^9, 0 \leq q_i \leq 3 \times 10^5, \sum_{i=1}^m q_i \leq 3 \times 10^5)$ , representing that Aloha would rent bikes $q_i$ times on Day $p_i$ . It is guaranteed that $p_1, p_2, \cdots, p_m$ are distinct.

#include<bits/stdc++.h> using namespace std; int n,m,r,f[300005],a[300005]; int l[505],d[505],k[505],c[505]; signed main() { ios::sync_with_stdio(0); cin>>n>>m>>r; for(int i=1;i<=n;i++) cin>>d[i]>>k[i]>>c[i],l[i]=1; int len=0; for(int i=1,p,q;i<=m;i++) { cin>>p>>q; while(q--) a[++len]=p; } sort(a+1,a+len+1); for(int i=1;i<=len;i++) { f[i]=f[i-1]+r; for(int j=1;j<=n;j++) { while(i-l[j]+1>k[j]||a[i]-a[l[j]]+1>d[j]) { l[j]++; if(l[j]>i)break; } f[i]=min(f[i],f[l[j]-1]+c[j]); } //cerr<<f[i]<<endl; } cout<<f[len]<<endl; }

详情