oj.uz

Submission #260169

# Submission time Handle Problem Language Result Execution time Memory
260169 2020-08-09T13:05:57 Z jdh Colouring a rectangle (eJOI19_colouring) C++17
0 / 100
 132 ms 15352 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 1 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 1 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 1 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 1 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 119 ms 15352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 132 ms 9208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 1 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -