Submission #519667

#	Time	Username	Problem	Language	Result	Execution time	Memory
519667		jjjjj19980806	Aliens (IOI16_aliens)	C++14	16 / 100	101 ms	1280 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];
}

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);
  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);
      |   ^~~~~

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