Course Override

    1#include <bits/stdc++.h>
    2 
    3using namespace std;
    4// Oh I just realized it is not a greedy problem
    5// should have looked at the constraint
    6//it is a backtracking/dp question
    7//大意了没有闪
    8struct course {
    9    int s, f, b, e, m, v, total;
    10};
    11int n, m;
    12vector<course> a;
    13bool bad[21][21];
    14bool chose[21];
    15long long best = -1;
    16// index is next course to consider
    17// count is how many chosen so far
    18// sum is total value so far
    19void dfs(int indx, int cnt, long long sum){
    20    if (cnt + (n - indx) < m) return; // stop if we cannot reach m even if we pick all courses
    21    if(indx == n){
    22        if(cnt >= m){
    23            best = max(best, sum);
    24            return;
    25        }
    26    }
    27    //if mandatory, we must include it 
    28    if(a[indx].m){
    29        bool good = true;
    30        //check if conflict with previously chosen courses
    31        for(int i = 0; i < indx; i++){
    32            if(chose[i] && bad[indx][i]){
    33                good = false;
    34                break;
    35            }
    36        }
    37        if(good){
    38            chose[indx] = true;
    39            dfs(indx + 1, cnt + 1, sum + a[indx].total);
    40            chose[indx] = false;
    41        } // if we cannot chose mandatory, we cannot proceed with the current arrangement since mandatory cannot be satisfied 
    42    } else {
    43        //skip optional course
    44        dfs(indx + 1, cnt, sum);
    45        // if no conflict, try including it
    46        bool good = true;
    47         //check if conflict with previously chosen courses
    48        for(int i = 0; i < indx; i++){
    49            if(chose[i] && bad[indx][i]){
    50                good = false;
    51                break;
    52            }
    53        }
    54        if(good){
    55            chose[indx] = true;
    56            dfs(indx + 1, cnt + 1, sum + a[indx].total);
    57            chose[indx] = false;
    58        }
    59    }
    60}
    61int main(){
    62    ios::sync_with_stdio(0);
    63    cin.tie(0);
    64    cin >> n >> m;
    65    a.resize(n);
    66    for(int i = 0; i < n; i++){
    67        cin >> a[i].s >> a[i].f >> a[i].b >> a[i].e >> a[i].m >> a[i].v;
    68        a[i].total = (a[i].f - a[i].s + 1) * (a[i].e - a[i].b + 1) * a[i].v;
    69    }
    70    //preprocess conflicting 
    71    for(int i = 0; i < n; i++){
    72        for(int j = i + 1; j < n; j++){
    73            bool bad_day = !(a[i].f < a[j].s || a[j].f < a[i].s); // i finishes before j starts or j finishes before i starts
    74            bool bad_time = !(a[i].e < a[j].b || a[j].e < a[i].b); // the same for time
    75            if(bad_day && bad_time) bad[i][j] = bad[j][i] = true; // conflict if on same day and at same time
    76        }
    77    }
    78    //check if mandatory days conlfict each other or not , if yes then it is impossible 
    79    int count = 0;
    80    for(int i = 0; i < n; i++){
    81        if(a[i].m){ // mandatory 
    82            count++;
    83            for(int j = i + 1; j < n; j++){
    84                if(a[j].m && (bad[i][j] || bad[j][i])){
    85                    cout << -1 << '\n';
    86                    return 0;
    87                }
    88            }
    89        }
    90    }
    91    dfs(0, 0, 0LL);
    92    cout << best << '\n';
    93    return 0;
    94}