Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- "use strict";
- const scanf = require( 'scanf' );
- class CombinationList {
- constructor( values ) {
- this._values = values;
- this._combinations = [];
- }
- addCombination( bonus, comb ) {
- let self = this;
- let combination = [];
- let total = bonus;
- comb.forEach(function( c ) {
- total -= self._values[ c ];
- combination[c] = true;
- });
- this._combinations.push({
- c: combination,
- total: total
- });
- }
- join( i1, i2 ) {
- const cout = {
- c: [],
- total: 0
- };
- const c1 = this._combinations[ i1 ];
- const c2 = this._combinations[ i2 ];
- let total = c1.total + c2.total;
- for ( let i = 0; i < this._values.length; ++i ) {
- if ( c1.c[i] && c2.c[i] ) {
- total += this._values[i];
- }
- cout.c[i] = c1.c[i] || c2.c[i];
- }
- cout.total = total;
- return cout;
- }
- optimize() {
- const max = this._combinations.length;
- let skiped = [];
- let running = true;
- while ( running ) {
- running = false;
- for ( let i = 0; i < max; ++i ) {
- const c = this._combinations[ i ];
- for ( let j = i+1; j<max; ++j ) {
- if ( skiped[j] === true )
- continue;
- const joined = this.join( i, j );
- if ( joined.total > c.total ) {
- c.c = joined.c;
- c.total = joined.total;
- running = true;
- skiped[j] = true;
- }
- }
- }
- }
- const compacted = [];
- for ( let i = 0; i < max; ++i ) {
- if ( ( skiped[i] === true ) || ( this._combinations[i].total < 0 ) )
- continue;
- compacted.push( this._combinations[i] );
- }
- this._combinations = compacted;
- }
- getTotal() {
- let total = 0;
- this._combinations.forEach(function( c ) {
- total += c.total;
- });
- return total;
- }
- }
- function main() {
- const nVodkas = scanf( "%d" );
- const nCombs = scanf( "%d" );
- const values = [];
- for ( let i = 0; i < nVodkas; ++i )
- values.push( scanf( "%d" ) );
- const combCount = [];
- for ( let i = 0; i < nCombs; ++i )
- combCount.push( scanf( "%d" ) );
- const list = new CombinationList( values );
- for ( let i = 0; i < nCombs; ++i ) {
- const bonus = scanf( "%d" );
- const used = [];
- for ( let j = 0; j < combCount[i]; ++j ) {
- used.push( scanf( "%d" ) - 1 );
- }
- list.addCombination( bonus, used );
- }
- list.optimize();
- console.log( list.getTotal() );
- }
- main();
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement