1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
#include<algorithm>
#include<cstring>
using namespace std;
namespace io{
#define re register
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3f
#define il inline
#define in1(a) read(a)
#define in2(a,b) in1(a),in1(b)
#define in3(a,b,c) in2(a,b),in1(c)
#define in4(a,b,c,d) in2(a,b),in2(c,d)
il void (ll &x){
x=0;ll f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
x*=f;
}
il void read(int &x){
x=0;int f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
x*=f;
}
}using namespace io;
#define N 505
#define M 10005
int m,e,n;
int d[N],q[M];
ll f[N][M];
struct node{
int x,a,c;
}s[N];
bool cmp(node a,node b){
return a.x<b.x;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("data.in","r",stdin);
#endif
in3(m,e,n);
for(re int i=1;i<=n;i++) in3(s[i].x,s[i].a,s[i].c);
sort(s+1,s+n+1,cmp);
n++;
s[n].x=e;
for(re int i=2;i<=n;i++) d[i]=s[i].x-s[i-1].x;
for(re int i=0;i<=n;i++) for(re int j=1;j<=m;j++) f[i][j]=inf;
for(re int i=1;i<=n;i++){
int head=1,tail=1;
q[1]=0;
for(re int j=1;j<=m;j++){
while(head<=tail&&j-q[head]>s[i].a) head++;
if(f[i-1][j]!=inf){
while(head<=tail&&f[i-1][q[tail]]-1ll*q[tail]*s[i].c>=f[i-1][j]-1ll*j*s[i].c){
tail--;
}
q[++tail]=j;
}
if(head<=tail){
int k=q[head];
f[i][j]=f[i-1][k]+1ll*(j-k)*s[i].c+1ll*j*j*d[i+1];
}
}
}
printf("%lld",f[n][m]);
return 0;
}
|
近期评论