Submission #386137

#	Time	Username	Problem	Language	Result	Execution time	Memory
386137		tko919	Aliens (IOI16_aliens)	C++17	25 / 100	413 ms	4460 KiB

aliens

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;

//template
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ALL(v) (v).begin(),(v).end()
using ll=long long int;
const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12;
template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
//end

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
   using P=pair<int,int>;
   vector<P> pos,used;
   rep(i,0,n){
      if(r[i]>c[i])swap(r[i],c[i]);
      pos.push_back({r[i],c[i]});
   }
   sort(ALL(pos),[](P& a,P& b){
      if(a.first==b.first)return a.second>b.second;
      else return a.first<b.first;
   });
   int mx=-1;
   rep(i,0,n){
      if(!chmax(mx,pos[i].second))continue;
      used.push_back(pos[i]);
   }

   n=used.size();
   int nxt=1;
   ll from[510][510],to[510][510];
   rep(i,0,n+5)rep(j,0,k+5)from[i][j]=INF;
   from[0][0]=0;
   for(auto& p:used){
      rep(i,0,n+5)rep(j,0,k+5)to[i][j]=INF;
      rep(i,0,n+5)rep(j,0,k+1)if(from[i][j]!=INF){
         if(p!=used.back()){
            chmin(to[i][j],from[i][j]);
         }
         ll add=1LL*(p.second-used[i].first+1)*(p.second-used[i].first+1);
         if(i){
            if(used[i-1].second>=used[i].first){
               add-=1LL*(used[i-1].second-used[i].first+1)*(used[i-1].second-used[i].first+1);
            }
         }
         chmin(to[nxt][j+1],from[i][j]+add);
      }
      swap(from,to);
      nxt++;
   }

   ll res=INF;
   rep(j,1,k+1)chmin(res,from[n][j]);
   return res;
}

/*
int main() {
    int n, m, k;
    assert(3 == scanf("%d %d %d", &n, &m, &k));
    std::vector<int> r(n), c(n);
    for (int i = 0; i < n; i++) {
        assert(2 == scanf("%d %d", &r[i], &c[i]));
    }
    long long ans = take_photos(n, m, k, r, c);
    
    
    printf("%lld\n", ans);
    return 0;
}
//*/

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