Advertisement
Guest User

Untitled

a guest
Aug 29th, 2016
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. "use strict";
  2.  
  3. const scanf = require( 'scanf' );
  4.  
  5. class CombinationList {
  6.  
  7.     constructor( values ) {
  8.         this._values       = values;
  9.         this._combinations = [];
  10.     }
  11.  
  12.     addCombination( bonus, comb ) {
  13.         let self = this;
  14.  
  15.         let combination = [];
  16.         let total = bonus;
  17.         comb.forEach(function( c ) {
  18.             total -= self._values[ c ];
  19.             combination[c] = true;
  20.         });
  21.         this._combinations.push({
  22.             c: combination,
  23.             total: total
  24.         });
  25.     }
  26.    
  27.     join( i1, i2 ) {
  28.         const cout = {
  29.             c: [],
  30.             total: 0
  31.         };
  32.         const c1 = this._combinations[ i1 ];
  33.         const c2 = this._combinations[ i2 ];
  34.        
  35.         let total = c1.total + c2.total;
  36.         for ( let i = 0; i < this._values.length; ++i ) {
  37.             if ( c1.c[i] && c2.c[i] ) {
  38.                 total += this._values[i];
  39.             }
  40.             cout.c[i] = c1.c[i] || c2.c[i];
  41.         }
  42.         cout.total = total;
  43.         return cout;
  44.     }
  45.  
  46.     optimize() {
  47.         const max = this._combinations.length;
  48.         let skiped = [];
  49.         let running = true;
  50.         while ( running ) {
  51.             running = false;
  52.             for ( let i = 0; i < max; ++i ) {
  53.                 const c = this._combinations[ i ];
  54.                 for ( let j = i+1; j<max; ++j ) {
  55.                     if ( skiped[j] === true )
  56.                         continue;
  57.                    
  58.                     const joined = this.join( i, j );
  59.                     if ( joined.total > c.total ) {
  60.                         c.c     = joined.c;
  61.                         c.total = joined.total;
  62.                         running = true;
  63.                         skiped[j] = true;
  64.                     }
  65.                 }
  66.             }
  67.         }
  68.  
  69.         const compacted = [];
  70.         for ( let i = 0; i < max; ++i ) {
  71.             if ( ( skiped[i] === true ) || ( this._combinations[i].total < 0 ) )
  72.                 continue;
  73.             compacted.push( this._combinations[i] );
  74.         }
  75.         this._combinations = compacted;
  76.     }
  77.  
  78.     getTotal() {
  79.         let total = 0;
  80.         this._combinations.forEach(function( c ) {
  81.             total += c.total;
  82.         });
  83.         return total;
  84.     }
  85. }
  86.  
  87. function main() {
  88.  
  89.     const nVodkas = scanf( "%d" );
  90.     const nCombs  = scanf( "%d" );
  91.    
  92.     const values = [];
  93.     for ( let i = 0; i < nVodkas; ++i )
  94.         values.push( scanf( "%d" ) );
  95.    
  96.     const combCount = [];
  97.     for ( let i = 0; i < nCombs; ++i )
  98.         combCount.push( scanf( "%d" ) );
  99.  
  100.  
  101.     const list = new CombinationList( values );
  102.     for ( let i = 0; i < nCombs; ++i ) {
  103.         const bonus = scanf( "%d" );
  104.         const used  = [];
  105.         for ( let j = 0; j < combCount[i]; ++j ) {
  106.             used.push( scanf( "%d" ) - 1 );
  107.         }
  108.         list.addCombination( bonus, used );
  109.     }
  110.  
  111.     list.optimize();
  112.     console.log( list.getTotal() );
  113.  
  114. }
  115. main();
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement