显示代码纯文本
#include<bits/stdc++.h>
#define long long ll
using namespace std;
int n,b,a[200000],d[200000],l[200000];
int f[3000][3000];//第一维 靴子,第二维 位置
int main(){
freopen("snowboots_silver_18feb.in","r",stdin);
freopen("snowboots_silver_18feb.out","w",stdout);
cin>>n>>b;
f[1][1]=1;
for(int q=1;q<=n;q++) cin>>a[q];
for(int q=1;q<=b;q++) cin>>d[q]>>l[q];
for(int q=1;q<=b;q++)
{
for(int w=1;w<=n;w++)
{
if(f[q-1][w]==1) f[q][w]=2;
if(f[q-1][w]>0&&d[q]>=a[w]) f[q][w]=1;
if(f[q][w]==1)
{
for(int e=1;e<=l[q];e++)
{
if(d[q]>=a[w+e]) f[q][w+e]=1;
}
}
}
}
int k;
for(int q=1;q<=b;q++)
{
if(f[q][n]==1)
{
k=q;
break;
}
}
cout<<k-1;
return 0;
}