fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. bool cmp(pair<long long,long long>a,pair<long long,long long>b)
  4. {
  5.     return a.first<b.first;
  6. }
  7. int n,k,a[400005],vt,x[400005],d,n1;
  8. long long s,f[400005],tr[400005],Min,Min1;
  9. set<pair<long long,int> > st;
  10. int main()
  11. {
  12.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  13.     //freopen("bottles.inp","r",stdin);
  14.     //freopen("bottles.out","w",stdout);
  15.     cin>>n>>k;
  16.     for (int i=1;i<=n;i++){cin>>a[i];s+=a[i];}
  17.     if(k>n)
  18.     {
  19.         cout<<n<<' '<<s<<'\n';
  20.         for(int i=1;i<=n;i++)cout<<i<<' ';
  21.         return 0;
  22.     }
  23.     for(int i=1;i<=k;i++){f[i]=a[i];st.insert(make_pair(a[i],i));}
  24.     for(int i=k+1;i<=n;i++)
  25.     {
  26.         f[i]=(*st.begin()).first+a[i];tr[i]=(*st.begin()).second;
  27.         st.erase(st.find(make_pair(f[i-k],i-k)));st.insert(make_pair(f[i],i));
  28.     }
  29.     Min=1e18;
  30.     for(int i=n-k+1;i<=n;i++)
  31.     {
  32.         if(Min>f[i])
  33.         {
  34.             vt=i;
  35.             Min=f[i];
  36.         }
  37.     }
  38.     n1=n;
  39.     while(tr[vt]!=0)
  40.     {
  41.         a[vt]=0;
  42.         vt=tr[vt];
  43.         n1--;
  44.     }
  45.     a[vt]=0;
  46.     n1--;
  47.     cout<<n1<<' '<<s-Min<<'\n';
  48.     for(int i=1;i<=n;i++)
  49.     {
  50.         if(a[i]>0)cout<<i<<' ';
  51.     }
  52.     return 0;
  53. }
  54.  
Success #stdin #stdout 0s 5696KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1 -1000000000000000000
https://ideone.com/qviZm0
language:
C++14 (clang 8.0)
created:
7 days ago
visibility:
public

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!