点击查看代码
#include<bits/stdc++.h>
using namespace std;const int N=10010,M=1010,INF=0x3f3f3f3f;
int n,m,k;
int u[N],d[N];
int l[N],h[N];
int f[N][M];int main()
{ios::sync_with_stdio(0),cin.tie(0);cin>>n>>m>>k;for(int i=0;i<=n-1;i++){cin>>u[i]>>d[i];}for(int i=1;i<=n;i++) l[i]=0,h[i]=m+1;for(int i=0;i<k;i++){int p;cin>>p;cin>>l[p]>>h[p];}memset(f,0x3f,sizeof f);for(int j=0;j<=m;j++) f[0][j]=0;int pipes=0;for(int i=1;i<=n;i++){int x=u[i-1],y=d[i-1];//处理上升的情况for(int j=1;j<=m;j++){if(j>x) f[i][j]=min(f[i][j],min(f[i-1][j-x]+1,f[i][j-x]+1));}//判断超过边界的情况for(int j=max(1,m-x+1);j<=m;j++){f[i][m]=min(f[i][m],min(f[i-1][j]+1,f[i][j]+1));}//处理下降的情况for(int j=1;j<=m-y;j++){f[i][j]=min(f[i][j],f[i-1][j+y]);}bool safe=false;for(int j=1;j<=m;j++){if(j<=l[i]||j>=h[i]) f[i][j]=INF;if(f[i][j]<INF) safe=true;}if(!safe){cout<<'0'<<endl<<pipes<<endl;return 0;}if(l[i]>0||h[i]<m+1) pipes++;}int ans=INF;for(int j=1;j<=m;j++) ans=min(ans,f[n][j]);cout<<'1'<<endl<<ans<<endl;return 0;
}