mickypinata

PROG-T1036: Equipped

Aug 5th, 2021
745
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 1e5;
  5.  
  6. int cost[N + 1], dp[N + 2][1 << 8];
  7. bool tasks[N + 1][8];
  8.  
  9. int main(){
  10.  
  11.     int nItem, task;
  12.     scanf("%d%d", &nItem, &task);
  13.     for(int i = 1; i <= nItem; ++i){
  14.         scanf("%d", &cost[i]);
  15.         for(int j = 0; j < task; ++j){
  16.             scanf("%d", &tasks[i][j]);
  17.         }
  18.     }
  19.     for(int i = 1; i <= nItem + 1; ++i){
  20.         dp[i][(1 << task) - 1] = 0;
  21.     }
  22.     for(int btw = 0; btw < (1 << task); ++btw){
  23.         dp[nItem + 1][btw] = 1e9;
  24.     }
  25.     for(int i = nItem; i >= 1; --i){
  26.         for(int btw = (1 << task) - 2; btw >= 0; --btw){
  27.             int newBtw = btw;
  28.             for(int j = 0; j < task; ++j){
  29.                 if(tasks[i][j]){
  30.                     newBtw |= (1 << j);
  31.                 }
  32.             }
  33.             dp[i][btw] = min(cost[i] + dp[i + 1][newBtw], dp[i + 1][btw]);
  34.         }
  35.     }
  36.     cout << dp[1][0];
  37.  
  38.     return 0;
  39. }
  40.  
RAW Paste Data