Submission #837079

#	Time	Username	Problem	Language	Result	Execution time	Memory
837079		erdemkiraz	Aliens (IOI16_aliens)	C++17	0 / 100	2031 ms	86860 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int M = 1e6 + 5;

int n, m, k;
int at[M];
vector<ii> v;

vector<vector<vector<ll>>> dp;

ll f(int x, int last, int k) {
  if(x > m + 1) {
    return 0;
  }

  ll &r = dp[x][last][k];
  if(r != -1) {
    return r;
  }

  r = 1e18;

  if(!at[x] or last >= at[x]) {
    // printf("x = %d last = %d k = %d\n", x, last, k);
    r = min(r, f(x + 1, last, k));
  }

  if(k) {
    int y = x + 1;
    if(at[x] > last) {
      y = at[x];
    }
    for(; y <= m + 1; y++) {
      ll len = y - x;
      r = min(r, f(x + 1, y, k - 1) + len * len);
    }
  }

  // printf("x = %d last = %d k = %d at = %d r = %lld\n", x, last, k, at[x], r);

  return r;
}

ll take_photos(int nn, int mm, int kk, vector<int> r, vector<int> c) {
  n = nn;
  m = mm;
  k = kk;

  for(int i = 0; i < n; i++) {
    if(r[i] > c[i]) {
      swap(r[i], c[i]);
    }
    at[r[i] + 1] = max(at[r[i] + 1], c[i] + 2);
  }
  sort(v.begin(), v.end());

  dp.resize(m + 2, vector<vector<ll>>(m + 2, vector<ll>(k + 1, -1)));

  ll ans = f(1, 0, k);

  return ans;
}

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