Main » 2013 October 16 » [模拟赛NOIP2010]集卡片
9:09 AM [模拟赛NOIP2010]集卡片 |
贪心，坑了#include<cstdio> #include<cstdlib> #include<cstring> #include<set> #include<algorithm> #include<map> #include<vector> #include<queue> #include<iostream> #include<string> #include<cmath> #define M 2010 #define N 1000010 #define FOR(i,a,b) for(i=(a);i<=(b);i++) #define ROF(i,a,b) for(i=(a);i>=(b);i--) typedef long long LL; using namespace std; int n,m,i,p,F[M],times[N],a[N],t[M],v,sum[N]; inline int getint() { register int num=0; register char ch; do ch=getchar(); while (ch<'0' || ch>'9'); do num=num*10+ch-'0', ch=getchar(); while (ch>='0' && ch<='9'); return num; } int main() { scanf("%d%d%d",&n,&m,&v); FOR(i,1,m) t[i]=getint(); int L=0,last=-2e9; FOR(i,1,n) { p=getint(); if (p==last) times[L]++; else {a[++L]=p;last=p;times[L]=1;} } sum[0]=0; FOR(i,1,L) sum[i]=sum[i-1]+times[i]*t[a[i]]; int ans=-2e9;int cnt=0; memset(F,0,sizeof(F)); int p=1; FOR(i,1,L) { F[a[i]]++; if (F[a[i]]==1) cnt++; while ((F[a[p]]>1)&&(p<i)) {F[a[p]]--;p++;} if (cnt==m) { int st=p,ed=i,d; d=sum[ed-1]-sum[st+1-1]+t[a[st]]+t[a[ed]]; if (v-d>ans) ans=v-d; } } if (ans<0) printf("NO ans\n"); else printf("%d\n",ans); } |
|
|
| Total comments: 0 | |