网络流
h<=50?
直接都选择最大的，ans=n*h*h
最小割
考虑舍弃或者罚款
有一个>x就要罚款？
经典取值限制的模型：切糕割！
每个位置的x+1到额外点tot连接inf边
tot向t连接c边
大概这样：
#include<bits/stdc++.h>
#define reg register int
#define il inline
#define fi first
#define se second
#define mk(a,b) make_pair(a,b)
#define numb (ch^'0')
#define pb push_back
#define solid const auto &
#define enter cout<<endl
#define pii pair<int,int>
using namespace std;
typedef long long ll;
template<class T>il void rd(T &x){
char ch;x=0;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*10+numb);
(fl==true)&&(x=-x);
}
template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+'0');}
template<class T>il void ot(T x){if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}
template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}
namespace Miracle{
const int N=55;
const int P=N*N;
const int inf=0x3f3f3f3f;
int n,m,h;
int s,t;
struct node{
int nxt,to;
int w;
}e[2*(P+P+N*N)];
int hd[P],cnt=1;
void add(int x,int y,int z){
e[++cnt].nxt=hd[x];
e[cnt].to=y;e[cnt].w=z;
hd[x]=cnt;
e[++cnt].nxt=hd[y];
e[cnt].to=x;e[cnt].w=0;
hd[y]=cnt;
}
int d[P];
int q[P],l,r;
int ans;
int dfs(int x,int flow){
int res=flow;
if(x==t) return flow;
for(reg i=hd[x];i&&res;i=e[i].nxt){
int y=e[i].to;
if(d[y]==d[x]+1&&e[i].w){
int k=dfs(y,min(res,e[i].w));
if(!k) d[y]=0;
res-=k;
e[i].w-=k;
e[i^1].w+=k;
}
}
return flow-res;
}
bool bfs(){
memset(d,0,sizeof d);
l=1,r=0;
q[++r]=s;
d[s]=1;
while(l<=r){
int x=q[l++];
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
if(e[i].w&&!d[y]){
d[y]=d[x]+1;
q[++r]=y;
if(y==t) return true;
}
}
}
return false;
}
int num(int x,int y){
return (x-1)*(h+1)+y+1;
}
int main(){
rd(n);rd(h);rd(m);
ans=n*h*h;
s=0;t=num(n,h)+1;
int tot=t;
for(reg i=1;i<=n;++i){
add(s,num(i,0),inf);
for(reg j=0;j<h;++j){
add(num(i,j),num(i,j+1),h*h-j*j);
}
}
int l,r,x,c;
for(reg i=1;i<=m;++i){
rd(l);rd(r);rd(x);rd(c);
if(x<h){
++tot;
add(tot,t,c);
for(reg j=l;j<=r;++j){
add(num(j,x+1),tot,inf);
}
}
}
int flow=0;
while(bfs()){
while(flow=dfs(s,inf)) ans-=flow;
}
ot(ans);
return 0;
}
}
signed main(){
Miracle::main();
return 0;
}
/*
Author: *Miracle*
*/