frp

E - AC

frp
May 16th, 2011
190
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.13 KB | None | 0 0
  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4. typedef unsigned char uchar;
  5. typedef unsigned uint;
  6. int a[30000];
  7. int mlc[25001];
  8.  
  9. bool res[30000];
  10. int main()
  11. {
  12.     uint n;scanf("%u",&n);
  13.     uint sum=0;
  14.     for(int i=0;i<n;i++)
  15.     {
  16.         scanf("%u",&a[i]);
  17.         sum+=a[i];
  18.     }
  19.     uint osum=sum;
  20.     sum>>=1;
  21.     mlc[0]=0;
  22.     for(int i=1;i<=sum;i++)mlc[i]=-1;
  23.     uint currsum=0;
  24.     for(int i=0;i<n;i++)
  25.     {
  26.         bool bf=false;
  27.         currsum=min(currsum+a[i],sum);
  28.         for(int j=currsum;j>=0;j--)
  29.             if(mlc[j]!=-1 && j+a[i]<=currsum && mlc[j+a[i]]==-1)
  30.             {
  31.                 mlc[j+a[i]]=i;
  32.                 if(j+a[i]==sum)
  33.                 {
  34.                     bf=true;
  35.                     break;
  36.                 }
  37.             }
  38.         if(bf)break;
  39.     }
  40.     int mj=0;
  41.     for(mj=sum;mj>=0;mj--)if(mlc[mj]!=-1)break;
  42.     printf("%u %u\n",mj,osum-mj);
  43.     int p=mj;
  44.     while(p>0)
  45.     {
  46.         if(mlc[p]==-1)break;
  47.         res[mlc[p]]=true;
  48.         p=p-a[mlc[p]];
  49.     }
  50.     bool fst=true;
  51.     for(int i=0;i<n;i++)
  52.         if(res[i])
  53.         {
  54.             if(fst)fst=false;
  55.             else printf(" ");
  56.             printf("%d",i+1);
  57.         }
  58.     printf("\n");
  59.     fst=true;
  60.     for(int i=0;i<n;i++)
  61.         if(!res[i])
  62.         {
  63.             if(fst)fst=false;
  64.             else printf(" ");
  65.             printf("%d",i+1);
  66.         }
  67.         printf("\n");
  68.     return 0;
  69. }
Advertisement
Add Comment
Please, Sign In to add comment