fork(1) download
copy 
  1. #include <stdio.h>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. #define BACKPACKS_NUMBER 2
  6.  
  7. struct Item {
  8.   int id, value, size;
  9. };
  10.  
  11. struct Backpack {
  12.   int max_size, current_size;
  13.   std::vector<Item> items;
  14. };
  15.  
  16. void getInputs(std::vector<Item> &, Backpack [], int &);
  17. void packBackpacks(std::vector<Item>, Backpack []);
  18. bool sortByValue(Item &, Item &);
  19. void printAnswer(Backpack[]);
  20. bool sortById(Item &, Item &);
  21.  
  22. int main(){
  23.   std::vector<Item> all_items;
  24.   Backpack backpacks[BACKPACKS_NUMBER] = {};
  25.   int items_number = 0, i = 0;
  26.  
  27.   getInputs(all_items, backpacks, items_number);
  28.   std::sort(all_items.begin(), all_items.end(), sortByValue);
  29.   packBackpacks(all_items, backpacks);
  30.   printAnswer(backpacks);
  31.  
  32.   return 0;
  33. }
  34.  
  35. void getInputs(std::vector<Item> &all_items, Backpack backpacks[], int &items_number){
  36.   int i = 0;
  37.  
  38.   scanf("%i", &items_number);
  39.   scanf("%i", &backpacks[0].max_size);
  40.   scanf("%i", &backpacks[1].max_size);
  41.  
  42.   for(; i < items_number; i++){
  43.     Item item;
  44.     item.id = i+1;
  45.  
  46.     scanf("%i", &item.value);
  47.     scanf("%i", &item.size);
  48.  
  49.     all_items.push_back(item);
  50.   }
  51. }
  52.  
  53. void packBackpacks(std::vector<Item> all_items, Backpack backpacks[]){
  54.   for(int i = 0; i < all_items.size(); i++){
  55.     bool isAdded = false;
  56.     for(int c = 0; c < BACKPACKS_NUMBER; c++){
  57.       if(!isAdded){
  58.         if(backpacks[c].current_size + all_items[i].size <= backpacks[c].max_size){
  59.           isAdded = true;
  60.           backpacks[c].current_size += all_items[i].size;
  61.           backpacks[c].items.push_back(all_items[i]);
  62.         }
  63.       } else {
  64.         break;
  65.       }
  66.     }
  67.   }
  68. }
  69.  
  70. bool sortByValue(Item &a, Item &b){
  71.   return a.value > b.value;
  72. }
  73.  
  74. void printAnswer(Backpack backpacks[]){
  75.   int max_value = 0, i = 0, c = 0; 
  76.   for(; i < BACKPACKS_NUMBER; i++){
  77.     for(c = 0; c < backpacks[i].items.size(); c++){
  78.       max_value += backpacks[i].items[c].value;
  79.     }
  80.   }
  81.   printf("%d\n", max_value);
  82.  
  83.   for(i = 0; i < BACKPACKS_NUMBER; i++){
  84.     std::sort(backpacks[i].items.begin(), backpacks[i].items.end(), sortById);
  85.     for(c = 0; c < backpacks[i].items.size(); c++){
  86.       printf("%d ", backpacks[i].items[c].id);
  87.     }
  88.     printf("%c", '\n');
  89.   }
  90. }
  91.  
  92. bool sortById(Item &a, Item &b){
  93.   return a.id < b.id;
  94. }
  95.  
Success #stdin #stdout 0.01s 5436KB
comments (?)
stdin
copy 
6 4 3
4 1
6 2
3 2
2 1
1 1
3 3
stdout
copy 
16
1 2 4 
3 5
https://ideone.com/ZIU7tC
problem ETI07E7, based on SPOJ submission 30343225 (CPP14-CLANG), 2022-11-02 12:23:49
language:
C++14 (clang 8.0)
created:
1 year ago
visibility:
secret

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!