fork download 
  1. #define ll long long
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. int main()
  5. {
  6.     ll t;
  7.  
  8.     scanf("%lld",&t);
  9.  
  10.     while(t--)
  11.     {
  12.        ll n,k,i,a,l,r=5e9,j,tot,ans,mx;
  13.        ll cnt=0;
  14.        scanf("%lld %lld",&n,&k);
  15.        vector<ll>v;
  16.        for(i=0;i<n;i++)
  17.        {
  18.            scanf("%lld",&a);
  19.            v.push_back(a);
  20.            l = a;
  21.        }
  22.  
  23.       l = v[n-1];
  24.       while(l<r)
  25.       {
  26.           ll tot = 0;
  27.           ll cnt = 0;
  28.          ll  mid = (l+r)/2;
  29.           for(i=0;i<n;i++)
  30.           {
  31.               if(tot+v[i]<=mid)
  32.               {
  33.                   tot+=v[i];
  34.               }
  35.  
  36.               else
  37.               {
  38.                   tot = v[i];
  39.                   cnt++;
  40.               }
  41.           }
  42.  
  43.           if(cnt<k)
  44.           {
  45.               ans = mid;
  46.               r = mid;
  47.           }
  48.  
  49.           else
  50.             l = mid+1;
  51.  
  52.  
  53.       // cout<<mid<<" "<<l<<" "<<r<<" "<<ans<<" "<<cnt<<endl;
  54.       }
  55.     //cout<<ans<<endl;
  56.     cnt = k-1;
  57.     ll sum=0;
  58.     map<ll,ll>mp;
  59.     for(i=n-1;i>=0;i--)
  60.     {
  61.        if(sum+v[i]>ans||cnt>i)
  62.        {
  63.            mp[i]=1;
  64.            sum = v[i];
  65.            cnt--;
  66.        }
  67.  
  68.        else
  69.         sum+=v[i];
  70.     }
  71.  
  72.     for(i=0;i<n;i++)
  73.     {
  74.         printf("%lld ",v[i]);
  75.  
  76.         if(mp[i])
  77.         {
  78.             printf("/ ");
  79.         }
  80.     }
  81.  
  82.     printf("\n");
  83.  
  84.     }
  85. }
  86.  
Success #stdin #stdout 0s 4300KB
comments (?)
stdin 
8
5 3
1 2 5 7 10
6 4
1 1 1 1 1 1000
2 1
1 1000
3 3
1 2 3
10 6
1 2 5 6 8 20 50 80 300 480
1 1
1000
3 3
1 1 100
10 5
1 1 1 1 1 1 1 1 1 1000
stdout 
1 2 5 / 7 / 10 
1 / 1 / 1 1 1 / 1000 
1 1000 
1 / 2 / 3 
1 / 2 / 5 / 6 / 8 20 50 80 300 / 480 
1000 
1 / 1 / 100 
1 / 1 / 1 / 1 1 1 1 1 1 / 1000
https://ideone.com/208mbi
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!