Submission #1052367

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052367		cjoa	Aliens (IOI16_aliens)	C++17	12 / 100	67 ms	6648 KiB

aliens

#include "aliens.h"

#include <bits/stdc++.h>

using namespace std;

int N, K, M;
vector<int> R;

const long long INF = 1e18 + 123;

const int MAXN = 1000;

bool cached[MAXN+1][MAXN+1];
long long memo[MAXN+1][MAXN+1];

// dp(i) = minima suma de areas que cubren los puntos desde i hasta N-1
long long dp( int i, int rem_fotos ) {
   if (i == N)
      return 0;

   if (cached[i][rem_fotos])
      return memo[i][rem_fotos];

   long long res = INF;
   if (rem_fotos > 0) {
      for (int j = i; j < N; j++) {
         long long area_foto = (R[j] - R[i] + 1) * 1LL * (R[j] - R[i] + 1);
         long long cur = area_foto + dp( j + 1, rem_fotos-1 );
         res = min(res, cur);
      }
   }
   
   cached[i][rem_fotos] = true;
   memo[i][rem_fotos] = res;
   
   return res;
}


long long take_photos(int n, int m, int k,
                      std::vector<int> r, std::vector<int> c) {
   N = n;
   R = r;
   sort(R.begin(), R.end());
   K = k;
   M = m;

   for (int i = 0; i < n; i++)
      for (int k = 0; k <= n; k++)
         cached[i][k] = false;

   return dp( 0, K );
}

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