Submission #69473

#	Time	Username	Problem	Language	Result	Execution time	Memory
69473		funcsr	Aliens (IOI16_aliens)	C++17	25 / 100	2054 ms	29756 KiB

aliens

#include "aliens.h"
#include <iostream>
#include <algorithm>
#define rep(i, n) for (int i=0; i<(n); i++)
#define pb push_back
#define INF (1LL<<60)
#define all(x) (x).begin(), (x).end()
#define _1 first
#define _2 second
using namespace std;
typedef pair<int, int> P;

struct CHT {
  vector<pair<long long, long long> > ps;
  void add(long long x, long long y) {
    ps.pb(make_pair(x, y));
  }
  long long min(long long x) {
    long long m = INF;
    for (auto p : ps) m = std::min(m, p._1*x+p._2);
    return m;
  }
};
CHT dp[4001];
int L[100000], R[100000];

long long take_photos(int N, int M, int K, vector<int> RR, vector<int> CC) {
  vector<P> ins;
  rep(i, N) {
    int l = min(RR[i], CC[i]), r = max(RR[i], CC[i]);
    ins.pb(P(l, -r));
  }
  sort(all(ins));
  vector<P> ins2;
  int lp = -1;
  for (P p : ins) {
    int l = p._1, r = -p._2;
    if (lp < r) {
      ins2.pb(P(l, r));
      lp = r;
    }
  }
  swap(ins, ins2);
  N = ins.size();
  rep(i, N) L[i] = ins[i]._1, R[i] = ins[i]._2;
  //rep(i, N) cout << "["<<ins[i]._1<<","<<ins[i]._2<<"]\n";
  K = min(K, N);

  dp[0].add(L[0], 1LL*L[0]*L[0]);
  long long ans = INF;
  rep(x, N) {
    for (int k=K-1; k>=0; k--) {
      long long m = dp[k].min(-2LL*(R[x]+1));
      if (m == INF) continue;
      m += 1LL*(R[x]+1)*(R[x]+1);
      // cout<<"dp["<<x<<"]["<<k+1<<"]="<<m<<"\n";
      if (x==N-1) {
        ans = min(ans, m);
      }
      else {
        long long overlap = 0;
        if (L[x+1]<=R[x]) overlap = 1LL*(R[x]-L[x+1]+1)*(R[x]-L[x+1]+1);
        dp[k+1].add(L[x+1], m+1LL*L[x+1]*L[x+1]-overlap);
      }
    }
  }
  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