oj.uz

Submission #200991

# Submission time Handle Problem Language Result Execution time Memory
200991 2020-02-09T04:16:52 Z model_code Domino (COCI15_domino) C++17
160 / 160
 1089 ms 159848 KB 
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <utility>
#include <tuple>

using namespace std;

const int MAXN = 2005;
const int MAXK = 9;
typedef pair <int, int> pii;
typedef long long llint;

int n, k;
int mat[MAXN][MAXN];

struct Field {
  pii pos;
  bool dir;
  int sum;

  Field (pii pos = pii(0, 0), bool dir = 0) : pos(pos), dir(dir) {
    int x, y;
    tie(x, y) = pos;
    sum = mat[x][y] + mat[x + dir][y + (1 - dir)];
  }

  vector <pii> get_fields () const {
    int x, y;
    tie(x, y) = pos;
    vector <pii> ret;
    ret.push_back(pii(x, y));
    ret.push_back(pii(x + dir, y + (1 - dir)));
    return ret;
  }


  bool intersect (const Field &B) const {
    auto Af = get_fields();
    auto Bf = B.get_fields();
    for (auto a: Af)
      for (auto b: Bf)
	if (a == b) return true;
    return false;
  }
};

bool cmp (const Field &A, const Field &B) {
  return A.sum > B.sum;
}

short val[MAXN];
llint mask[MAXN];

short best_left[1 << 20][MAXK];

void solve_left (int pos, int sz, int cmask, llint blocked, short sum, int cnt) {
  if (cnt > k) return;
  if (pos == sz) {
    best_left[cmask][cnt] = sum;
    return;
  }
  solve_left(pos+1, sz, cmask, blocked, sum, cnt);
  if (!(blocked & (1LL << pos)))
    solve_left(pos+1, sz, cmask | (1LL << pos), blocked | mask[pos], sum + val[pos], cnt + 1);
}


int solve_right (int pos, int sz, int szl, llint blocked, short sum, int cnt) {
  if (cnt > k) return 0;
  if (pos == sz){
    return sum + best_left[(~blocked) & ((1 << szl) - 1)][k - cnt];
  }

  int ret = solve_right(pos+1, sz, szl, blocked, sum, cnt);
  if (!(blocked & (1LL << pos)))
    ret = max(ret, solve_right(pos+1, sz, szl, blocked | mask[pos], sum + val[pos], cnt + 1));
  return ret;
}

int solve (int sz) {
 int lsz = sz / 2;
  while (lsz > 20) --lsz;

  solve_left(0, lsz, 0, 0, 0, 0);
  for (int i = 0; i < (1 << lsz); ++i) {
    int pos = i;
    while (pos > 0) {
      int bit = pos&-pos;
      for (int j = 0; j <= k; ++j)
	best_left[i][j] = max(best_left[i][j], best_left[i - bit][j]);
      pos -= bit;
    }
  }
  return solve_right(lsz, sz, lsz, 0, 0, 0);
}

int main (void){
  scanf("%d%d", &n, &k);
  vector <Field> V;
  V.reserve(n*n*2);
  long long sum = 0;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j) {
      scanf("%d", &mat[i][j]);
      sum += mat[i][j];
    }

  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j) {
      V.push_back(Field(pii(i, j), 0));
      V.push_back(Field(pii(i, j), 1));
    }

  int sz = min((int)V.size(), (k - 1)*7 + 1);
  nth_element(V.begin(), V.begin() + sz, V.end(), cmp);

  for (int i = 0; i < sz; ++i)
    val[i] = V[i].sum;

  for (int i = 0; i < sz; ++i)
    for (int j = 0; j < sz; ++j)
      if (V[i].intersect(V[j])) mask[i] |= (1LL << j);

  printf("%lld\n", sum - solve(sz));
  return 0;
}

Compilation message

domino.cpp: In function 'int main()':
domino.cpp:100:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &n, &k);
   ~~~~~^~~~~~~~~~~~~~~~
domino.cpp:106:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &mat[i][j]);
       ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 11128 KB Output is correct
2 Correct 44 ms 11128 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 636 KB Output is correct
2 Correct 5 ms 632 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 714 ms 141432 KB Output is correct
2 Correct 606 ms 141432 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 82644 KB Output is correct
2 Correct 326 ms 82552 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 39544 KB Output is correct
2 Correct 155 ms 39544 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 743 ms 141728 KB Output is correct
2 Correct 573 ms 141560 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 5240 KB Output is correct
2 Correct 29 ms 5240 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 693 ms 146168 KB Output is correct
2 Correct 622 ms 145912 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 19576 KB Output is correct
2 Correct 130 ms 19704 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1528 KB Output is correct
2 Correct 11 ms 1528 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 853 ms 159764 KB Output is correct
2 Correct 772 ms 159848 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 19320 KB Output is correct
2 Correct 151 ms 19320 KB Output is correct

Subtask #14
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 549 ms 58028 KB Output is correct
2 Correct 331 ms 58104 KB Output is correct

Subtask #15
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 18808 KB Output is correct
2 Correct 135 ms 18936 KB Output is correct

Subtask #16
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1089 ms 159776 KB Output is correct
2 Correct 751 ms 159736 KB Output is correct