TASK: fence8
LANG: C++
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.000 secs, 3032 KB]
Test 2: TEST OK [0.000 secs, 3032 KB]
Test 3: TEST OK [0.000 secs, 3032 KB]
Test 4: TEST OK [0.000 secs, 3032 KB]
Test 5: TEST OK [0.000 secs, 3032 KB]
Test 6: TEST OK [0.027 secs, 3032 KB]
Test 7: TEST OK [0.000 secs, 3032 KB]
Test 8: TEST OK [0.000 secs, 3032 KB]
Test 9: TEST OK [0.000 secs, 3032 KB]
Test 10: TEST OK [0.000 secs, 3032 KB]
Test 11: TEST OK [0.000 secs, 3032 KB]
Test 12: TEST OK [0.000 secs, 3032 KB]
All tests OK.
1 /*
2 ID: jiafeim1
3 LANG: C++
4 TASK: fence8
5 */
6 #include<stdio.h>
7 #include<algorithm>
8 using namespace std;
9 int n,r,m;
10
11 int orig[52],target[1055];
12 int prett[1055];
13 int total=0;
14 int tempOrig[52];
15 int mid;
16 int minTarget;
17 int space;
18 bool doit(int targetpos,int origpos)
19 {
20 if(targetpos<=0) return true;
21 if(space + prett[mid]>total) return false;
22 for(int i = origpos ;i<=n;++i)
23 if(target[targetpos]<=tempOrig[i])
24 {
25 tempOrig[i]-=target[targetpos];
26 if(tempOrig[i]<minTarget)
27 space += tempOrig[i];
28
29 if(target[targetpos]==target[targetpos-1])
30 {
31 if(doit(targetpos-1,i)) return true;
32 }
33 else
34 if(doit(targetpos-1,1)) return true;
35
36 if(tempOrig[i]<minTarget)
37 space -= tempOrig[i];
38
39 tempOrig[i]+=target[targetpos];
40 }
41 return false;
42 }
43
44 int main()
45 {
46
47 FILE *fin,*fout;
48 fin = fopen("fence8.in","r");
49 fout = fopen("fence8.out","w");
50 fscanf(fin,"%d",&n);
51 for(int i = 1;i<=n;++i)
52 {
53 fscanf(fin,"%d",orig+i);
54 total+=orig[i];
55 }
56
57 fscanf(fin,"%d",&m);
58 for(int i = 1;i<=m;++i)
59 {
60 fscanf(fin,"%d",target+i);
61 }
62 sort(orig+1,orig+n+1);
63 sort(target+1,target+m+1);
64 minTarget = target[1];
65 orig[0]=prett[0]=target[0]=0;
66
67 for(int i = 1;i<=m;++i)
68 {
69 prett[i] += prett[i-1]+target[i];
70 }
71 while(prett[m]>total) --m;
72 int left=0,right=m;
73 mid = (left+right)/2;
74
75 while(left<=right)
76 {
77 space = 0;
78 for(int i = 1;i<=n;++i) tempOrig[i] = orig[i];
79 if(doit(mid,1))
80 {
81 left = mid + 1;
82 mid = (right+left)/2;
83 }
84 else
85 {
86 right = mid - 1;
87 mid = (right +left)/2;
88 }
89
90 }
91 fprintf(fout,"%d\n",mid);
92 fclose(fin);
93 fclose(fout);
94
95 return 0;
96 }