Submission #837303

#	Time	Username	Problem	Language	Result	Execution time	Memory
837303		erdemkiraz	Aliens (IOI16_aliens)	C++17	25 / 100	2045 ms	22356 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<int> ats;
vector<ii> v;
 
vector<vector<ll>> dp;
 
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);
  }

  v.push_back({0, 0});

  for(int i = 1; i <= m + 1; i++) {
    if(at[i]) {
      if(!ats.empty() and ats.back() >= at[i]) {
        continue;
      }
      ats.push_back(at[i]);
      v.push_back({i, at[i]});
    }
  }

  // ats.push_back(0);

  // sort(ats.begin(), ats.end());
  // ats.resize(unique(ats.begin(), ats.end()) - ats.begin());

  // for(auto& [x, y] : v) {
  //   y = lower_bound(ats.begin(), ats.end(), y) - ats.begin();
  // }

  m = (int) v.size() - 1;
 
  dp.resize(m + 1, vector<ll>(k + 1, 1e18));

  for(int i = 0; i <= k; i++) {
    dp[0][i] = 0;
  }

  for(int rem = 1; rem <= k; rem++) {
    for(int j = 1; j <= m; j++) {
        for(int i = j; i >= 1; i--) {
        int prev = v[i - 1].second;
        int x = v[i].first;
        int y = v[j].second;

        ll len = y - x;
        ll inter = max(0, prev - x);
        dp[j][rem] = min(dp[j][rem], dp[i - 1][rem - 1] + len * len - inter * inter);
      }
    }
  }
 
  ll ans = dp[m][k];
 
  return ans;
}

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