Submission #260169

#	Time	Username	Problem	Language	Result	Execution time	Memory
260169		jdh	Colouring a rectangle (eJOI19_colouring)	C++17	0 / 100	132 ms	15352 KiB

colouring

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n,m;
  cin >> n >> m;
  vector<ll> cost1(n+m-1),cost2(n+m-1);
  for(int i = 0; i < n+m-1; ++i) cin >> cost1[i];
  for(int i = 0; i < n+m-1; ++i) cin >> cost2[i];
  if(m == 1){
    ll ans = 0;
    for(int i = 0; i < n+m-1; ++i) ans += min(cost1[i],cost2[i]);
    cout << ans;
    return 0;
  }
  ll ans = LLONG_MAX;
  for(int i = 0; i < (1<<(n+m-1)); ++i){
    ll tmp = 0;
    vector<vector<bool>> vu(n,vector<bool>(m));
    for(int j = 0; j < n+m-1; ++j){
      if(i&(1<<j)){
        tmp += cost1[j];
        int delta = i-(m-1);
        for(int x = 0; x < n; ++x){
          int y = x-delta;
          if(0 <= y and y < m) vu[x][y] = true;
        }
      }
    }
    set<int> st;
    for(int x = 0; x < n; ++x){
      for(int y = 0; y < m; ++y){
        if(!vu[x][y]){
          st.insert(x+y);
        }
      }
    }
    for(int j : st){
      tmp += cost2[j];
    }
    ans = min(ans,tmp);
  }
  cout << ans;
  return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 10
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20