Editorial for Pizza Location
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
type ar=array[1..100] of boolean; var n,k,m,re,r:longint; a:array[1..20,0..1] of longint; b:array[1..100,0..2] of longint; d:array[1..100,1..20] of boolean; f:array[1..20] of longint; c,e:ar; procedure rf; var i:longint; begin readln(k,r); readln(m); for i:=1 to m do readln(a[i,0],a[i,1]); readln(n); for i:=1 to n do readln(b[i,0],b[i,1],b[i,2]); end; procedure init; var i,j,t:longint; begin for j:=1 to m do for i:=1 to n do if sqr(a[j,0]-b[i,0])+sqr(a[j,1]-b[i,1])<=r*r then begin d[i,j]:=true; inc(f[j],b[i,2]); end; end; procedure att(i,j:longint;var s:longint;e:ar); var p,q,t:longint; begin if (i>k) or (j>m) then begin if s>re then re:=s; exit; end; for p:=j to m-k+i do begin if (i=k) and (f[p]+s<=re) then continue; t:=0; fillchar(e,sizeof(e),false); for q:=1 to n do if (not c[q]) and d[q,p] then begin t:=t+b[q,2]; c[q]:=true; e[q]:=true; end; s:=s+t; att(i+1,p+1,s,e); for q:=1 to n do if e[q] then c[q]:=false; s:=s-t; end; end; procedure pr; var i,j,s:longint; begin init; re:=0; s:=0; att(1,1,s,e); writeln(re); end; begin rf; pr; end.
Code mẫu của happyboy99x
#include<cstdio> #include<algorithm> using namespace std; #define M 20+5 #define N 100+5 int a[M][N]; int rx[M], ry[M], hx[N], hy[N], p[N]; //restaurant x, y, house x, y, people int k, r, m, n, inRange[N], now, res; inline int sqr(int x) { return x*x; } void init() { for(int i = 0; i < m; ++i) for(int j = 0; j < n; ++j) if(sqr(hx[j]-rx[i]) + sqr(hy[j]-ry[i]) <= r) a[i][++a[i][0]] = j; } void enter() { scanf("%d%d%d",&k,&r,&m); r *= r; for(int i = 0; i < m; ++i) scanf("%d%d",rx+i,ry+i); scanf("%d",&n); for(int i = 0; i < n; ++i) scanf("%d%d%d",hx+i,hy+i,p+i); } void backtrack(int q, int x) { if(k-q > m-x) return; if(q == k) res = max(now, res); else for(int i = x; i < m; ++i) { for(int j = 1; j <= a[i][0]; ++j) if(inRange[a[i][j]]++ == 0) now += p[a[i][j]]; backtrack(q+1, i+1); for(int j = 1; j <= a[i][0]; ++j) if(--inRange[a[i][j]] == 0) now -= p[a[i][j]]; } } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif enter(); init(); backtrack(0, 0); printf("%d\n", res); return 0; }
Code mẫu của ladpro98
program pizzaloc; uses math; type pizzares=record x,y:longint; end; house=record x,y,s:longint; end; arr=array[0..11] of longint; const lim=10; maxn=123; maxm=21; fi=''; var pos:array[1..maxn] of pizzares; a:array[1..maxn] of house; bit:array[0..maxn,0..maxn] of longint; p:array[0..maxn,0..1 shl lim] of longint; cs:arr; k,r,m,n,res,mp:longint; procedure input; var inp:text; i:longint; begin assign(inp,fi);reset(inp); readln(inp,k,r); readln(inp,m); for i:=1 to m do readln(inp,pos[i].x,pos[i].y); readln(inp,n); for i:=1 to n do readln(inp,a[i].x,a[i].y,a[i].s); close(inp); end; function getbit(i,j:longint):longint; begin exit(i shr (j-1) and 1); end; procedure init; var k,i,j:longint; begin r:=sqr(r); mp:=n div lim; for i:=1 to m do begin for j:=1 to n do if (r>=(sqr(pos[i].x-a[j].x)+sqr(pos[i].y-a[j].y))) then begin if j mod lim<>0 then inc(bit[i,j div lim],1 shl (j mod lim-1)) else inc(bit[i,j div lim-1],1 shl (lim-1)); end; end; for k:=0 to n div lim do for i:=0 to 1 shl lim-1 do begin for j:=1 to lim do if getbit(i,j)=1 then inc(p[k,i],a[j+k*lim].s); end; end; procedure back(i,c:longint; s:arr); var j,t:longint; begin if (c>=k) then begin t:=0; for j:=0 to mp do inc(t,p[j,s[j]]); res:=max(res,t); exit; end; if i>m then exit; if (k-c)<=(m-i) then back(i+1,c,s); for j:=0 to mp do s[j]:=s[j] or bit[i,j]; back(i+1,c+1,s); end; begin input; init; back(1,0,cs); write(res); end.
Code mẫu của RR
#include <iostream> #include <algorithm> #include <cmath> #define MAXN 111 #define FOR(i,a,b) for(long i=a; i<=b; i++) using namespace std; long k,r,m,x[MAXN],y[MAXN],n,x2[MAXN],y2[MAXN],s[MAXN],res,kq[MAXN]; long mask[MAXN],S; long sqr(long u) { return u*u; } void inp() { scanf("%ld %ld %ld",&k,&r,&m); FOR(i,1,m) scanf("%ld %ld",&x[i],&y[i]); scanf("%ld",&n); FOR(i,1,n) scanf("%ld %ld %ld ",&x2[i],&y2[i],&s[i]); FOR(i,1,n) { FOR(j,1,m) if (sqr(x2[i]-x[j])+sqr(y2[i]-y[j])<=r*r) mask[i]+=1L<<(j-1); } } void update() { long sum=0; FOR(i,1,n) if (S&mask[i]) sum+=s[i]; res=max(res,sum); } void duyet(long i) { if (i>k) { update(); return ; } FOR(j,kq[i-1]+1,m-k+i) { S+=1L<<(j-1); kq[i]=j; duyet(i+1); S-=1L<<(j-1); } } void solve() { duyet(1); printf("%ld\n",res); } int main() { inp(); solve(); return 0; }
Code mẫu của hieult
#include <stdio.h> //#include <conio.h> struct toado { int x,y; }; struct cuahang { public: int sch,a[101]; }; int main() { //freopen("PIZZALOC.in","r",stdin); int k,r,m,n,nguoi[101]; toado A[21],B[101]; cuahang ch[21]; scanf("%d %d",&k,&r); scanf("%d",&m); for(int i = 1;i<=m;i++) { //printf("1\n"); //ch[i].sch = 0; scanf("%d %d",&A[i].x,&A[i].y); } // printf("2\n"); scanf("%d",&n); for(int i = 1;i<=n ; i++) scanf("%d %d %d",&B[i].x,&B[i].y,&nguoi[i]); for(int i = 1;i<=m;i++) { // printf("3\n"); ch[i].sch = 0; // printf("4\n"); for(int j = 1;j<=n;j++) if((A[i].x-B[j].x)*(A[i].x-B[j].x)+(A[i].y-B[j].y)*(A[i].y-B[j].y)<= r*r) { ch[i].sch++; ch[i].a[ch[i].sch] = j; } } int u[k+1],flag[101],KQ = 0; for(int i = 1;i<=k;i++) u[i] = i; while(true) { //for(int i = 1;i<=k;i++) printf("%d ",u[i]); //printf("\n"); int max = 0; for(int i = 1 ;i<=n;i++) flag[i] = 0; for(int i = 1;i<=k;i++) for(int j = 1;j<=ch[u[i]].sch;j++) if(flag[ch[u[i]].a[j]]==0) { flag[ch[u[i]].a[j]]=1; max = max + nguoi[ch[u[i]].a[j]]; } // printf("_____%d____\n",max); if(max>KQ) KQ = max; if(u[k]<m) u[k]++; else { int fl = k-1; while(fl>0) { if(u[fl]+1!=u[fl+1]) break; fl--; } if(fl==0) break; else { u[fl]++; for(int i = fl+1;i<=k;i++) u[i] = u[i-1]+1; } } } printf("%d",KQ); //getch(); }
Code mẫu của ll931110
{$MODE DELPHI} Program PIZZALOC; Const input = ''; output = ''; maxn = 100; maxm = 20; Type rec = record x,y: integer; end; Var n,m,k,r,res,resmax: integer; s,e: array[1..maxn] of rec; num,es,curr: array[1..maxn] of integer; last: array[0..maxn] of integer; ser: array[1..maxm,1..maxn] of integer; free: array[1..maxm] of boolean; Procedure init; Var f: text; i: integer; Begin Assign(f, input); Reset(f); Readln(f, k, r); Readln(f, m); For i:= 1 to m do readln(f, s[i].x, s[i].y); Readln(f, n); For i:= 1 to n do Begin Read(f, e[i].x, e[i].y); Readln(f, num[i]); End; Close(f); End; Procedure gens; Var i,j,dis: integer; Begin Fillchar(es, sizeof(es), 0); For i:= 1 to m do For j:= 1 to n do Begin dis:= sqr(s[i].x - e[j].x) + sqr(s[i].y - e[j].y); If dis <= r * r then Begin inc(es[i]); ser[i,es[i]]:= j; End; End; Fillchar(free, sizeof(free), true); Fillchar(curr, sizeof(curr), 0); res:= 0; resmax:= 0; last[0]:= 0; End; Procedure attempt(i: integer); Var j,ij: integer; Begin For j:= last[i - 1] + 1 to m do if free[j] then Begin free[j]:= false; last[i]:= j; For ij:= 1 to es[j] do Begin If curr[ser[j,ij]] = 0 then res:= res + num[ser[j,ij]]; inc(curr[ser[j,ij]]); End; If i = k then Begin If resmax < res then resmax:= res; End else attempt(i + 1); free[j]:= true; For ij:= 1 to es[j] do Begin dec(curr[ser[j,ij]]); If curr[ser[j,ij]] = 0 then res:= res - num[ser[j,ij]]; End; End; End; Procedure printresult; Var f: text; Begin Assign(f, output); Rewrite(f); Writeln(f, resmax); Close(f); End; Begin init; gens; attempt(1); printresult; End.
Code mẫu của skyvn97
#include<stdio.h> #define MAX 250 struct pos { long x; long y; }; int k,n,m,r,sum,b; pos p[MAX]; pos h[MAX]; int s[MAX]; int sou[MAX]; bool c[MAX]; bool go[MAX][MAX]; void init(void) { scanf("%d",&k); scanf("%d",&r); scanf("%d",&m); int i,j; for (i=1;i<=m;i=i+1) { scanf("%ld",&p[i].x); scanf("%ld",&p[i].y); } scanf("%d",&n); for (i=1;i<=n;i=i+1) { scanf("%ld",&h[i].x); scanf("%ld",&h[i].y); scanf("%d",&s[i]); } for (i=1;i<=m;i=i+1) for (j=1;j<=n;j=j+1) { if ((p[i].x-h[j].x)*(p[i].x-h[j].x)+(p[i].y-h[j].y)*(p[i].y-h[j].y)<=r*r) go[i][j]=true; else go[i][j]=false; } for (i=1;i<=n;i=i+1) c[i]=false; sou[0]=0; b=0; } void update(void) { if (sum<=b) return; b=sum; } void btrk(int t) { int i,j,l; int tmp[MAX]; for (i=sou[t-1]+1;i+k-t<=m;i=i+1) { sou[t]=i; l=0; for (j=1;j<=n;j=j+1) { if ((go[i][j]) && (!c[j])) { l=l+1; c[j]=true; tmp[l]=j; sum=sum+s[j]; } } if (t==k) update(); else btrk(t+1); for (j=1;j<=l;j=j+1) { c[tmp[j]]=false; sum=sum-s[tmp[j]]; } } } int main(void) { init(); btrk(1); printf("%d",b); }
Comments