#include <stdio.h>#define N 2001#define inf 10000000#define max(a,b) ((a)>(b)?(a):(b))int f[N][N],q[N],id[N];
int main()
{
int t,n,maxp,w,ap,bp,as,bs; scanf("%d",&t);
while(t--){ scanf("%d%d%d",&n,&maxp,&w); for(int i=0;i<n;++i){ scanf("%d%d%d%d",&ap,&bp,&as,&bs); for(int j=0;j<=maxp;++j)f[i][j]=-inf; if(i<=w)for(int j=0;j<=as;++j)f[i][j]=-ap*j; if(i>0)for(int j=0;j<=maxp;++j)f[i][j]=max(f[i][j],f[i-1][j]); if (i==0||i<=w) continue; for(int j=0,l=0,r=-1;j<=maxp;++j){ int tmp=f[i-w-1][j]+j*ap; while(l<=r&&q[r]<tmp)--r; q[++r]=tmp,id[r]=j; while(l<=r&&id[l]+as<j)++l; f[i][j]=max(f[i][j],q[l]-j*ap);
} for(int j=maxp,l=0,r=-1;j>=0;--j){ int tmp=f[i-w-1][j]+j*bp; while(l<=r&&q[r]<tmp)--r; q[++r]=tmp,id[r]=j; while(l<=r&&id[l]-bs>j)++l; f[i][j]=max(f[i][j],q[l]-j*bp); } } int ans=0; for(int i=0;i<=maxp;++i)ans=max(ans,f[n-1][i]); printf("%d\n",ans); } return 0;
}
huicpc0860 2010-08-16 21:40 鍙戣〃璇勮
]]>using namespace std;
#define N 100010
#define max(x,y) ((x)>(y)?(x):(y))
typedef long long LL;
int s[N];
struct point {
int x, y;
point(){}
point(int x,int y):x(x),y(y){}
}p[N];
point operator - (const point &a, const point &b) { return point(a.x-b.x, a.y-b.y); }
LL operator ^ (const point &a, const point &b) { return (LL)a.x*b.y - (LL)a.y*b.x; }
inline int get(){
int s=0;
char c;
while(c=getchar(),c!=' '&&c!='\n')s=s*10+c-'0';
return s;
}
int main() {
int n,k;
s[0]=0;
while (~scanf("%d ",&n)){
k=get();n++;
for(int i=1;i<n;++i){
s[i]=get();
s[i]+=s[i-1];
}
double ans=0;
for(int i=k,m=-1,f=0;i<n;++i){
point now(i-k,s[i-k]);
while(f<m&&(p[m]-p[m-1]^now-p[m-1])<0)--m;
p[++m]=now;
while(f<m&&(LL)(s[i]-p[f].y)*(i-p[f+1].x)<(LL)(s[i]-p[f+1].y)*(i-p[f].x))f++;
ans=max(ans,double(s[i]-p[f].y)/(i-p[f].x));
}
printf("%.2lf\n",ans);
}
}
huicpc0860 2010-08-09 20:24 鍙戣〃璇勮
]]>huicpc0860 2010-08-01 20:05 鍙戣〃璇勮
]]>#include <stdio.h>#include <math.h>#include <algorithm>using namespace std;const double eps=1e-8;double h,ans,cake;struct point { double x,y; point (){} point (double x,double y):x(x),y(y){} void get(){scanf("%lf%lf",&x,&y);}};struct poly{ point p[21]; int n; void get(){for(int i=0;i<n;i++)p[i].get();p[n]=p[0];}}sg;int dcmp(double x){ return (x>eps)-(x<-eps);}double cross(point o,point p,point q){ return (p.x-o.x)*(q.y-o.y)-(p.y-o.y)*(q.x-o.x);}point lineinter(point a,point b,point c,point d){ double u=cross(a,b,c),v=cross(b,a,d); return point((c.x*v+d.x*u)/(u+v),(c.y*v+d.y*u)/(u+v));}double dis(point a,point b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}void push(point a,point b,point &c,point &d){ double x=a.y-b.y,y=b.x-a.x,t=h/dis(a,b); c=point(a.x+x*t,a.y+y*t); d=point(b.x+x*t,b.y+y*t);}void cut(point a,point b,poly tg,poly &g){ push(a,b,a,b); g.n=0; for(int i=0;i<tg.n;i++){ int u=dcmp(cross(a,b,tg.p[i])),v=dcmp(cross(a,b,tg.p[i+1])); if(u>=0)g.p[g.n++]=tg.p[i]; if(u*v<0) g.p[g.n++]=lineinter(a,b,tg.p[i],tg.p[i+1]); } g.p[g.n]=g.p[0];}double area(poly g){ double sum=0; for(int i=2;i<g.n;i++) sum+=cross(g.p[0],g.p[i-1],g.p[i]); return 0.5*sum;}void dfs(int i,int step,poly g){ if(step+i<sg.n)dfs(i+1,step,g); cut(sg.p[i],sg.p[i+1],g,g); if(step==1)ans=max(ans,cake-area(g)); else dfs(i+1,step-1,g);}int main(){ int k; while(scanf("%d%d%lf",&sg.n,&k,&h),sg.n||k||h){ sg.get(); cake=area(sg); ans=0; k=min(k,sg.n); if(k&&h)dfs(0,k,sg); printf("%.2lf\n",ans); } return 0;}
huicpc0860 2010-07-27 18:46 鍙戣〃璇勮
]]>#include <math.h>
#define max(a,b) (a>b?a:b)
int n;
struct seg {
double l, r, t;
} a[50];
int main() {
while (scanf("%d", &n), n) {
for (int i = 0; i < n; i++) {
scanf("%lf", &a[i].t);
a[i].l = 0.0;
for (int j = 0; j < i; j++)
a[i].l = max(a[i].l, a[j].r - fabs(a[i].t - a[j].t) / 2);
a[i].r = a[i].l + a[i].t;
}
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++)
if (a[i].l < a[i].r) {
if (a[i].t > a[j].t && a[i].l < a[j].r)
a[j].r = a[i].l;
else if (a[i].t < a[j].t && a[j].r > a[i].l)
a[i].l = a[j].r;
}
for (int i = 0; i < n; i++)
if (a[i].l < a[i].r)printf("%d ", i + 1);
puts("");
}
}
huicpc0860 2010-07-23 18:51 鍙戣〃璇勮
]]>#include <stdio.h>#include <algorithm>#include <string.h>using namespace std;struct point{ int x,y;}p[100010];int c[100010],n,d,a[100010],map[100010],t;bool cmp(point p0,point p1){ return p0.x<p1.x;}int lowbit(int x){ return x&(-x);}int sum(int x){ int s=0; while(x){ s=(s+c[x])%9901; x-=lowbit(x); } return s;}int update(int x,int y){ while(x<=n){ c[x]=(c[x]+y)%9901; x+=lowbit(x); }}int find(int x,bool y){ int l=1,r=n,m,ans=-1; if(y){ while(l<=r){ m=(l+r)>>1; if(p[m].x>=x){ ans=m; r=m-1; } else l=m+1; } }else{ while(l<=r){ m=(l+r)>>1; if(p[m].x<=x){ ans=m; l=m+1; } else r=m-1; } } return ans;}int main(){ while(scanf("%d%d",&n,&d)!=EOF){ memset(c,0,sizeof(c[0])*(n+1)); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); p[i].x=a[i]; p[i].y=i; } sort(p+1,p+n+1,cmp); for(int i=1;i<=n;i++)map[p[i].y]=i; for(int i=1;i<=n;i++){ int l=find(a[i]-d,1),r=find(a[i]+d,0); if(l+1&&r+1&&l<=r){ t=(9901+sum(r)-sum(l-1)+1)%9901;//+1宸у涔嬪錛岀敤浜庢爣璁版槸鍚﹁鏇存柊錛岀瓟妗堝啀鍑忓幓n鍗沖彲 update(map[i],t); } } printf("%d\n",(9901*20+sum(n)-n)%9901); } return 0;}
huicpc0860 2010-07-16 18:06 鍙戣〃璇勮
]]>#include <stdio.h>#include <algorithm>using namespace std;int cas,tim,n,x,y,a[60],b[60],f[210];int main(){ scanf("%d",&cas); for(int tim=0;tim<cas;){ scanf("%d%d%d",&n,&x,&y); for(int i=1;i<=n;i++)//涓嬫爣閲?寮濮?nbsp; scanf("%d%d",&a[i],&b[i]); int l=0,r=a[1]*x+b[1]*y,m; while(l<=r){ m=(l+r)>>1; for(int i=1;i<=x;i++)f[i]=-999999999; f[0]=0; for(int i=1;i<=n;i++) for(int v=x;v>=0;v--){ f[v]+=m/b[i];//鏂板叆宸ヤ漢瑕佹洿鏂?nbsp; for(int j=0;j<v;j++) if (m>=(v-j)*a[i]) f[v]=max(f[v],f[j]+(m-a[i]*(v-j))/b[i]); } if(f[x]>=y)r=m-1;//鏈宸﹂艱繎 else l=m+1; } printf("Case %d: %d\n",++tim,l); } return 0;}
huicpc0860 2010-07-15 20:26 鍙戣〃璇勮
]]>huicpc0860 2010-07-14 21:39 鍙戣〃璇勮
]]>#include <stdio.h>#include <stdlib.h>#include <string.h>#define lowbit(x) (x&(-x))bool c[1010][1010];int n;bool sum(int x,int y){ bool s=0; while(x){ int yy=y; while(yy){ s^=c[x][yy]; yy-=lowbit(yy); } x-=lowbit(x); } return s;}void update(int x,int y){ while(x<=n){ int yy=y; while(yy<=n){ c[x][yy]=!c[x][yy]; yy+=lowbit(yy); } x+=lowbit(x); }}int main(){ int t,x,y,xx,yy,m; char s[2]; scanf("%d",&t); while(t--){ memset(c,0,sizeof(c)); scanf("%d%d",&n,&m); while(m--){ scanf("%s",s); if(s[0]=='C'){ scanf("%d%d%d%d",&x,&y,&xx,&yy); update(++xx,++yy); update(x,yy); update(xx,y); update(x,y); }else{ scanf("%d%d",&x,&y); printf("%d\n",sum(x,y)); } } puts(""); } return 0;}
huicpc0860 2010-07-14 12:47 鍙戣〃璇勮
]]>//鎼滅儲鍏ラ棬 #include <stdio.h>#include <algorithm>using namespace std;int length,a[64],n,sum;bool ok,v[64]={0};void dfs(int i,int size,int step){ if(size==length)i=0,size=0,step--; if(step==0)ok=1; for(int old=-1;!ok&&i<n;i++) if(!v[i]&&a[i]!=old&&(size+a[i])<=length){ v[i]=1; old=a[i]; dfs(i+1,size+a[i],step); v[i]=0; if(size==0)return; }}bool cmp(int x,int y){return x>y;}int main(){ while(scanf("%d",&n),n){ sum=0,ok=0; for(int i=0;i<n;i++){scanf("%d",&a[i]);sum+=a[i];} sort(a,a+n,cmp); for(length=a[0];!ok&&length<=sum;length++) if(sum%length==0){ dfs(0,0,(sum/length)-1); if(ok)printf("%d\n",length); } } return 0;}
huicpc0860 2010-06-21 22:38 鍙戣〃璇勮
]]>