Advertisement
ismaeil

E2. Reading Books (hard version)

Jul 1st, 2020
135
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.66 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define S second
  4. #define F first
  5.  
  6. typedef long long ll;
  7. typedef pair<int, int> ii;
  8.  
  9.  
  10. vector<ii> Both ,Al ,Bob ,Zero;
  11. int n ,m ,k ,Ans;
  12. vector<int> ans;
  13.  
  14. void Exit() {
  15.     printf("-1");
  16.     exit(0);
  17. }
  18.  
  19. int main()
  20. {
  21.     scanf("%d%d%d",&n,&m,&k);
  22.  
  23.     for(int i=0 ; i<n ; i++) {
  24.         int t ,a ,b;
  25.         scanf("%d%d%d" ,&t ,&a ,&b);
  26.  
  27.         if( a && b )        Both.push_back({t, i});
  28.         else if( !a && b )  Bob.push_back( {t, i});
  29.         else if( a && !b )  Al.push_back ( {t, i});
  30.         else                Zero.push_back({t, i});
  31.     }
  32.  
  33.     sort(Zero.begin(), Zero.end());
  34.     sort(Both.begin(),Both.end());
  35.     sort(Bob.begin(),Bob.end());
  36.     sort(Al.begin(),Al.end());
  37.  
  38.     int idBoth = 0,idAl = 0,idBob = 0,idz = 0;
  39.     int szBoth = Both.size() ,szAl = Al.size(),
  40.         szBob = Bob.size()   ,szZ = Zero.size();
  41.  
  42.     int kAl = k,kBo = k;
  43.     while( m > 0 )
  44.     {
  45.             if( kAl > 0 && kBo > 0 )
  46.             {
  47.                     if( idAl < szAl && idBob < szBob && idBoth < szBoth )
  48.                     {
  49.                             if( Both[idBoth].F >= Al[idAl].F + Bob[idBob].F && m >= 2)
  50.                             {
  51.                                     Ans += Al[idAl].F + Bob[idBob].F;
  52.                                     ans.push_back( Al[idAl++].S );
  53.                                     ans.push_back( Bob[idBob++].S );
  54.                                     kAl --,kBo --, k--, m -= 2;
  55.                             }
  56.                             else
  57.                             {
  58.                                     Ans += Both[idBoth].F;
  59.                                     ans.push_back( Both[idBoth++].S );
  60.                                     kAl --,kBo --, k--, m -= 1;
  61.                             }
  62.                     }
  63.                     else if( idBoth == szBoth && (idAl == szAl || idBob == szBob) )
  64.                             Exit();
  65.                     else if( idBob == szBob || idAl == szAl )
  66.                     {
  67.                             Ans += Both[idBoth].F;
  68.                             ans.push_back( Both[idBoth++].S );
  69.                             kAl --,kBo --, k--, m -= 1;
  70.                     }
  71.                     else if( idBoth == szBoth && m >= 2 )
  72.                     {
  73.                             Ans += Al[idAl].F + Bob[idBob].F;
  74.                             ans.push_back( Al[idAl++].S );
  75.                             ans.push_back( Bob[idBob++].S );
  76.                             kAl --,kBo --, k--, m -= 2;
  77.                     }
  78.                     else Exit();
  79.             }
  80.             else
  81.             {
  82.                     vector<ii> all;
  83.                     for(int i = idBoth ; i < szBoth ; i++)
  84.                         all.push_back( Both[i] );
  85.                     for(int i = idAl ; i < szAl ; i++)
  86.                         all.push_back( Al[i] );
  87.                     for(int i = idBob ; i < szBob ; i++)
  88.                         all.push_back( Bob[i] );
  89.                     for(int i = idz ; i < szZ ; i++)
  90.                         all.push_back( Zero[i] );
  91.  
  92.                     sort(all.begin() ,all.end());
  93.                     k = -1;
  94.                     kAl = -1 ;
  95.                     kBo = -1 ;
  96.                     for(int i=0 ; i < (int)all.size() && m > 0 ; i++ ,m--){
  97.                             Ans += all[i].F;
  98.                             ans.push_back( all[i].S );
  99.                     }
  100.                     if( m > 0 ) Exit();
  101.             }
  102.     }
  103.  
  104.     if( max( kAl ,kBo ) <= 0 && m <= 0 ){
  105.         printf("%d\n",Ans);
  106.         for(auto i : ans)
  107.             printf("%d ",i + 1);
  108.     } else Exit();
  109.  
  110.     return 0;
  111. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement