Submission #837092

#	Time	Username	Problem	Language	Result	Execution time	Memory
837092		erdemkiraz	Aliens (IOI16_aliens)	C++17	4 / 100	2069 ms	311684 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<vector<ll>>> dp;
 
ll f(int x, int last, int k) {
  if(x >= m) {
    return 0;
  }
 
  ll &r = dp[x][last][k];
  if(r != -1) {
    return r;
  }
 
  r = 1e18;
 
  if(ats[last] >= ats[v[x].second]) {
    r = min(r, f(x + 1, last, k));
  }
 
  if(k) {
    // int mx = 0;
    // for(int y = x; y < m; y++) {
    //   mx = max(mx, v[y].second);

    //   if(ats[mx] <= ats[last]) {
    //     continue;
    //   }

    //   ll len = ats[mx] - v[x].first;
    //   ll prev_len = max(0, ats[last] - v[x].first);
    //   r = min(r, f(x + 1, mx, k - 1) + len * len - prev_len * prev_len);
    // }

    int mx = 0;
    int y = last + 1;
    if(ats[v[x].second] > ats[last]) {
      y = v[x].second;
    }

    for(; y < (int) ats.size(); y++) {
      ll len = ats[y] - v[x].first;
      ll prev_len = max(0, ats[last] - v[x].first);
      r = min(r, f(x + 1, y, k - 1) + len * len - prev_len * prev_len);
    }
  }

  // printf("x = %d last = %d k = %d r = %lld\n", x, last, k, 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);
  }

  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();
 
  dp.resize(m + 1, vector<vector<ll>>((int) ats.size() + 1, vector<ll>(k + 1, -1)));
 
  ll ans = f(0, 0, k);
 
  return ans;
}

Compilation message (stderr)

aliens.cpp: In function 'll f(int, int, int)':
aliens.cpp:49:9: warning: unused variable 'mx' [-Wunused-variable]
   49 |     int mx = 0;
      |         ^~

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