제출 #1020632

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1020632		huutuan	Aliens (IOI16_aliens)	C++14	25 / 100	2081 ms	22364 KiB

aliens

#include "aliens.h"

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int inf=1e18;

long long take_photos(int32_t n, int32_t m, int32_t k, vector<int32_t> r, vector<int32_t> c) {
   vector<pair<int, int>> v;
   for (int i=0; i<n; ++i){
      v.emplace_back(min(r[i], c[i]), max(r[i], c[i]));
   }
   sort(v.begin(), v.end());
   vector<pair<int, int>> v2;
   for (int i=0; i<(int)v.size(); ++i){
      int j=i;
      while (j+1<(int)v.size() && v[j+1].first==v[i].first) ++j;
      if (v2.empty() || v2.back().second<v[j].second) v2.push_back(v[j]);
      i=j;
   }
   n=v2.size();
   vector<vector<int>> f(n+1, vector<int>(k+1, inf));
   f[0][0]=0;
   for (int i=1; i<=n; ++i){
      for (int j=1; j<=k; ++j){
         for (int l=1; l<=i; ++l){
            int area=(v2[i-1].second-v2[l-1].first+1)*(v2[i-1].second-v2[l-1].first+1);
            if (l!=1 && v2[l-2].second>=v2[l-1].first) area-=(v2[l-2].second-v2[l-1].first+1)*(v2[l-2].second-v2[l-1].first+1);
            f[i][j]=min(f[i][j], f[l-1][j-1]+area);
         }
      }
   }
   return *min_element(f[n].begin(), f[n].end());
}

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