Submission #519852

#	Time	Username	Problem	Language	Result	Execution time	Memory
519852		jjjjj19980806	Aliens (IOI16_aliens)	C++14	41 / 100	119 ms	93924 KiB

aliens

#include "aliens.h"

#include <bits/stdc++.h>

#ifdef LOCAL
#include "../../codebook/debug.h"
#else
#define debug(...) 0516
#endif

using namespace std;

long long solve_1(int n, int m, int k, vector<int> &r, vector<int> &c) {
  vector<vector<bool>> g(m, vector<bool>(m));
  long long ans = 0;
  for (int i = 0; i < n; i++) {
    if (r[i] > c[i]) {
      swap(r[i], c[i]);
    }
    for (int x = r[i]; x <= c[i]; x++) {
      for (int y = r[i]; y <= c[i]; y++) {
        if (g[x][y] == false) {
          g[x][y] = true;
          ans += 1;
        }
      }
    }
  }
  return ans;
}

long long solve_2(int n, int m, int k, vector<int> &r, vector<int> &c) {
  sort(c.begin(), c.end());
  c.erase(unique(c.begin(), c.end()), c.end());
  n = c.size();

  vector<vector<int>> dp(n + 1, vector<int>(k + 1));
  for (int i = 1; i <= n; i++) {
    dp[i].assign(k + 1, m * m);
    for (int j = 1; j <= k; j++) {
      for (int t = 0; t <= i - 1; t++) {
        dp[i][j] = min(dp[i][j], dp[t][j - 1] + 
            (c[i - 1] - c[t] + 1) * (c[i - 1] - c[t] + 1));
      }
    }
  }
  debug(dp);

  return dp[n][k];
}

void clean(int &n, vector<int> &r, vector<int> &c) {
  for (int i = 0; i < n; i++) {
    if (r[i] > c[i]) swap(r[i], c[i]);
  }
  vector<int> order(n);
  iota(order.begin(), order.end(), 0);
  sort(order.begin(), order.end(), [&](int i, int j) {
      return make_pair(r[i], -c[i]) < make_pair(r[j], -c[j]);
    });
  
  vector<int> new_r, new_c;
  for (int i = 0; i < n; i++) {
    if (new_r.empty() || c[order[i]] > new_c.back()) {
      new_r.push_back(r[order[i]]);
      new_c.push_back(c[order[i]]);
    }
  }
  r = new_r;
  c = new_c;
  n = r.size();
}

long long solve_3(int n, int m, int k, vector<int> &r, vector<int> &c) {
  clean(n, r, c);
  debug(r);
  debug(c);
  
  // cost cover [i...j] and remove overlapping
  auto cost = [&](int i, int j) {
    int res = (c[j] - r[i] + 1) * (c[j] - r[i] + 1);
    if (i != 0) {
      int d = max(0, c[i - 1] - r[i] + 1);
      res -= d * d;
    }
    return res;
  };

  vector<vector<int>> dp(n + 1, vector<int>(k + 1));
  for (int i = 1; i <= n; i++) {
    dp[i].assign(k + 1, m * m);
    for (int j = 1; j <= k; j++) {
      for (int t = 1; t <= i; t++) {
        dp[i][j] = min(dp[i][j], dp[i - t][j - 1] + cost(i - t, i - 1));
      }
    }
  }

  debug(dp);
  return dp[n][k];
}

long long solve_4(int n, int m, int k, vector<int> &r, vector<int> &c) {
  clean(n, r, c);
  debug(r);
  debug(c);

  // cost cover [i...j] and remove overlapping
  auto cost = [&](int i, int j) {
    long long res = 1LL * (c[j] - r[i] + 1) * (c[j] - r[i] + 1);
    if (i != 0) {
      long long d = max(0, c[i - 1] - r[i] + 1);
      res -= d * d;
    }
    return res;
  };

  vector<vector<long long>> dp(k + 1, vector<long long>(n + 1));
  vector<vector<int>> opt(k + 1, vector<int>(n + 1));
  for (int i = 1; i <= n; i++) {
    dp[1][i] = cost(0, i - 1);
  }
  for (int i = 2; i <= k; i++) {
    for (int j = n; j > 0; j--) {
      dp[i][j] = dp[i - 1][j];
      int upper = j == n ? n - 1 : min(j - 1, opt[i][j + 1]);
      for (int t = opt[i - 1][j]; t <= upper; t++) {
        if (dp[i][j] > dp[i - 1][t] + cost(t, j - 1)) {
          dp[i][j] = dp[i - 1][t] + cost(t, j - 1);
          opt[i][j] = t;
        }
      }
    }
  }

  debug(dp);
  return dp[k][n];
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
  
  // if (n <= 50 && m <= 100 && k == n) return solve_1(n, m, k, r, c);
  // if (n <= 500 && m <= 1000 && r == c) return solve_2(n, m, k, r, c);
  // if (n <= 500 && m <= 1000) return solve_3(n, m, k, r, c);
  if (n <= 4000) return solve_4(n, m, k, r, c);
  return 0;    
}

Compilation message (stderr)

aliens.cpp: In function 'long long int solve_2(int, int, int, std::vector<int>&, std::vector<int>&)':
aliens.cpp:8:20: warning: statement has no effect [-Wunused-value]
    8 | #define debug(...) 0516
      |                    ^~~~
aliens.cpp:47:3: note: in expansion of macro 'debug'
   47 |   debug(dp);
      |   ^~~~~
aliens.cpp: In function 'long long int solve_3(int, int, int, std::vector<int>&, std::vector<int>&)':
aliens.cpp:8:20: warning: statement has no effect [-Wunused-value]
    8 | #define debug(...) 0516
      |                    ^~~~
aliens.cpp:76:3: note: in expansion of macro 'debug'
   76 |   debug(r);
      |   ^~~~~
aliens.cpp:8:20: warning: statement has no effect [-Wunused-value]
    8 | #define debug(...) 0516
      |                    ^~~~
aliens.cpp:77:3: note: in expansion of macro 'debug'
   77 |   debug(c);
      |   ^~~~~
aliens.cpp:8:20: warning: statement has no effect [-Wunused-value]
    8 | #define debug(...) 0516
      |                    ^~~~
aliens.cpp:99:3: note: in expansion of macro 'debug'
   99 |   debug(dp);
      |   ^~~~~
aliens.cpp: In function 'long long int solve_4(int, int, int, std::vector<int>&, std::vector<int>&)':
aliens.cpp:8:20: warning: statement has no effect [-Wunused-value]
    8 | #define debug(...) 0516
      |                    ^~~~
aliens.cpp:105:3: note: in expansion of macro 'debug'
  105 |   debug(r);
      |   ^~~~~
aliens.cpp:8:20: warning: statement has no effect [-Wunused-value]
    8 | #define debug(...) 0516
      |                    ^~~~
aliens.cpp:106:3: note: in expansion of macro 'debug'
  106 |   debug(c);
      |   ^~~~~
aliens.cpp:8:20: warning: statement has no effect [-Wunused-value]
    8 | #define debug(...) 0516
      |                    ^~~~
aliens.cpp:136:3: note: in expansion of macro 'debug'
  136 |   debug(dp);
      |   ^~~~~

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40