Submission #529131

#	Time	Username	Problem	Language	Result	Execution time	Memory
529131		msg555	Aliens (IOI16_aliens)	C++14	4 / 100	1 ms	256 KiB

aliens

#include "aliens.h"
  
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

long long squared(int x) {
  return 1ll * x * x;
}

long long take_photos(int N, int M, int K, vector<int> R, vector<int> C) {
  vector<pair<int, int> > A;
  for (int i = 0; i < N; i++) {
    int ri = R[i];
    int ci = C[i];
    if (ri > ci) swap(ri, ci);
    A.push_back(make_pair(ci, ci - ri));
  }
  sort(A.begin(), A.end());

  int j = 0;
  for (auto p : A) {
    while (j > 0 && p.second >= A[j - 1].second + p.first - A[j - 1].first) {
      --j;
    }
    A[j++] = p;
  }
  A.resize(j);
  N = j;

  vector<long long> DP(N + 1, 0);
  vector<long long> DP2(N + 1, 0);
  for (int k = 0; k < K; k++) {
    for (int i = 0; i < N; i++) {
      if (i) {
        DP[i] -= squared(max(0, 1 + A[i].second - A[i].first + A[i - 1].first));
      }

      DP2[i + 1] = squared(M);
      for (int j = 0; j <= i; j++) {
        DP2[i + 1] = min(
          DP2[i + 1],
          DP[j] + squared(1 + A[j].second + A[i].first - A[j].first)
        );
      }
    }

    DP.swap(DP2);
  }

  return DP[N];
}

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