2017"百度之星"程序设计大赛 - 资格赛

#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define rep(i,a,b) for (int i=a; i<=b; ++i)#define per(i,b,a) for (int i=b; i>=a; --i)#define mes(a,b)  memset(a,b,sizeof(a))#define INF 1e18#define MP make_pair#define PB push_back#define fi  first#define se  secondtypedef long long ll;const int N = 100005, M = 1005;int n, m, a[N], b[N], k[M], p[M];ll  dp[M][12];int main(){    while(~scanf("%d%d", &n, &m))    {        rep(i,1,n) scanf("%d%d", &a[i], &b[i]);        rep(i,1,m) scanf("%d%d", &k[i], &p[i]);        rep(bi,0,10) rep(i,0,M-1) {            if(i==0) dp[i][bi] = 0;            else dp[i][bi] = INF;        }        rep(bi,0,10) rep(ai,1,M-1) rep(i,1,m)            if(p[i]>bi)        {            if(ai-(p[i]-bi)>=0)                dp[ai][bi] = min(dp[ai-(p[i]-bi)][bi]+k[i], dp[ai][bi]);            else                dp[ai][bi] = min(1LL*k[i], dp[ai][bi]);        }        ll  ans = 0;        bool flag=0;        rep(i,1,n) {            if(dp[a[i]][b[i]]==INF) flag=1;            else ans += dp[a[i]][b[i]];        }        if(flag) puts("-1");        else printf("%I64d\n", ans);    }    return 0;}