Submission #555691

#	Time	Username	Problem	Language	Result	Execution time	Memory
555691		nots0fast	Aliens (IOI16_aliens)	C++17	25 / 100	2078 ms	6996 KiB

aliens

#include "aliens.h"
#include <fstream>
#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
#define mp(a,b) make_pair(a,b)
#define ff first
#define setp setprecision(12)<<fixed
#define ss second
#define fori(v) for(ll i=0; i<v; i++)
#define forj(v) for(ll j=0; j<v; j++)
#define fork(v) for(ll k=0; k<v; k++)
#define forl(v) for(ll l=0; l<v; l++)
#define fort(v) for(ll t=0; t<v; t++)
#define forz(v) for(ll z=0; z<v; z++)
#define forx(v) for(ll x=0; x<v; x++)
#define ll long long
#define lll __int128
#define ld long double
#define pb(a) push_back(a)
// #define cout out
// #define cin in
ll inf = pow(10, 18);
ll modulo = pow(10,9) + 7;
double eps = 1e-10;
ifstream in;
ofstream out;

bool J(pair<ll, ll>& a, pair<ll ,ll>& b){
      if(a.ff != b.ff){
            return a.ff < b.ff;
      }
      return a.ss > b.ss;
}


long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    
      vector<pair<ll, ll> > arr;
      fori(n){
            if(r[i] > c[i]){
                  swap(r[i], c[i]);
            }
            arr.pb(mp(r[i], c[i]));
      }
      
      sort(arr.begin(), arr.end(), J);
      ll mxc = -inf;
      {
            vector<pair<ll, ll> > good({mp(-1, -1)});
            fori(n){
                  ll ri = arr[i].ff, ci = arr[i].ss;
                  if(ci > mxc){
                        good.pb(mp(ri, ci));
                        mxc = ci;
                  }
            }
            arr = good;
      }
      /*
      cout<<"good is "<<endl;
      for(auto& el : arr){
          cout<<el.ff<<' '<<el.ss<<endl;
      }
      */
      n = arr.size();
      
      vector<vector<ll> > dp(n, vector<ll>(k+1, inf));
      dp[0][0] = 0;
      for(ll j = 1; j<=k; j++){
            for(ll i = 1; i<n; i++){
                  for(ll i1 = i-1; i1>=0; i1--){
                        
                        ll li = arr[i].ff, ri = arr[i].ss,
                        ri1 = arr[i1].ss, li2 = arr[i1+1].ff;
                        
                        ll cost = dp[i1][j-1] + (ri - li2 + 1) * (ri - li2 + 1);
                        if(ri1 >= li2){
                              cost -= (ri1-li2 + 1) * (ri1 - li2 + 1);
                        }
                        
                        dp[i][j] = min(dp[i][j],  cost);
                //        cout<<"at "<<i<<" for "<<j<<" pieces is "<<dp[i][j]<<endl;
                  }
            }
      }
      
      ll mn = inf;
      for(ll j = 0; j<=k; j++){
            mn = min(mn, dp[n-1][j]);
      }
      return mn;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:75:28: warning: unused variable 'li' [-Wunused-variable]
   75 |                         ll li = arr[i].ff, ri = arr[i].ss,
      |                            ^~

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