记录编号	560794	评测结果	AAAAAAAATTTTATTTTTTT
题目名称	[NOIP 2020]微信步数	最终得分	45
用户昵称	1111	是否通过	未通过
代码语言	C++	运行时间	11.716 s
提交时间	2021-05-12 20:33:09	内存使用	8.97 MiB

#include <bits/stdc++.h>
using namespace std;
const int N=5*100000+5;
const int K=10+5;
const int mod=1000000007;
int n,k;
long long ans=0;
int w[K],l[N],r[N],p[N]={0};
int c[N],d[N];
int main(){
	freopen ("2020walk.in","r",stdin);
	freopen ("2020walk.out","w",stdout);
	cin>>n>>k;
	for (int i=1;i<=k;i++){
		cin>>w[i];
	}
	for (int i=1;i<=n;i++){
		scanf("%d%d",&c[i],&d[i]);
	}
	for (int x=0;;x++){
		for (int i=1;i<=n;i++){
			p[c[i]]+=d[i];
			if (p[c[i]]<l[c[i]]||p[c[i]]>r[c[i]]){
				l[c[i]]=min(l[c[i]],p[c[i]]);
				r[c[i]]=max(r[c[i]],p[c[i]]);
				long long t=x*n+i;
				for (int j=1;j<=k;j++){
					if (w[j]+l[j]-r[j]<0){
						cout<<ans<<endl;
						return 0;
					}
					if (j!=c[i]){
						t=(t*(w[j]+l[j]-r[j])%mod)%mod;
					}
				}
				//cout<<t<<endl;
				ans=(ans+t)%mod;
			}
		}
		bool ok=0;
		for (int i=1;i<=k;i++){
			if (p[i]!=0){
				ok=1;break;
			}
		}
		if (ok==0){
			cout<<-1<<endl;
			return 0;
		}
	}

}