/* Link : http://www.lightoj.com/volume_showproblem.php?problem=1048 */ #include <bits/stdc++.h> #define pii pair <int,int> #define sc scanf #define pf printf #define Pi 2*acos(0.0) #define ms(a,b) memset(a, b, sizeof(a)) #define pb(a) push_back(a) #define MP make_pair #define oo 1<<29 #define dd double #define ll long long #define EPS 10E-10 #define ff first #define ss second #define MAX 10000 #define CIN ios_base::sync_with_stdio(0) #define SZ(a) (int)a.size() #define getint(a) scanf("%d",&a) #define getint2(a,b) scanf("%d%d",&a,&b) #define getint3(a,b,c) scanf("%d%d%d",&a,&b,&c) #define loop(i,n) for(int i=0;i<n;i++) #define TEST_CASE(t) for(int z=1;z<=t;z++) #define PRINT_CASE printf("Case %d: ",z) #define all(a) a.begin(),a.end() #define intlim 2147483648 #define inf 1000000 #define rtintlim 46340 #define llim 9223372036854775808 #define rtllim 3037000499 #define ull unsigned long long #define I int using namespace std; int ara[2000],n,m; bool test(int x) { int t=x; int cnt=0; for(int i=1; i<=n; i++) { if(x<ara[i]) return 0; if(t-ara[i]>=0) t-=ara[i]; else { cnt++; t=x-ara[i]; } if(cnt>m) return 0; } return 1; } int main() { ///freopen("in.txt","r",stdin); ///freopen("out.txt","w",stdout); int t; sc("%d",&t); TEST_CASE(t) { int sum=0,maxx=-1; getint2(n,m); n++; for(int i=1; i<=n; i++) { getint(ara[i]); maxx=max(maxx,ara[i]); sum+=ara[i]; } int l,r,mid; l=min(maxx,sum); r=max(maxx,sum); while(l<r) { mid=(l+r)/2; if(test(mid)) r=mid; else l=mid+1; } while(!test(mid)) mid++; m++; PRINT_CASE; pf("%d\n",mid); int temp=0; l=n; for(int i=1; i<=l; i++) { temp+=ara[i]; n--; m--; if(temp+ara[i+1]<=mid && n>m) { int j=i+1; temp+=ara[j]; n--; while(temp+ara[j+1]<=mid && n>m) { j++; temp+=ara[j]; n--; } i=j; } pf("%d\n",temp); temp=0; } } return 0; }
Here is another solution…
#include <bits/stdc++.h> using namespace std; int d[1024]; int main() { int t, tc = 0, n, i, j, k, hi, lo, mid, sum; scanf ("%d", &t); while (tc < t) { tc++; scanf ("%d%d", &n,&k); n++; k++; hi = 0; lo = 0; for (i = 0; i < n; i++) { scanf ("%d", &d[i]); hi += d[i]; } while (hi >= lo) { mid = (hi+lo)/2; for (i = 1, j = 0; i <= k ; i++) { sum = 0; for (; j < n; j++) { if (sum+d[j]>mid) break; sum += d[j]; } } if (j < n) lo = mid+1; else hi = mid-1; } printf ("Case %d: %d\n", tc, lo); for (i = k, j = 0; i > 0; i--) { sum = 0; for (; n-j >= i; j++) { if (sum+d[j] > lo) break; sum += d[j]; } printf ("%d\n",sum); } } return 0; }
can you please explain your idea? That would be great