Submission #334176

#	Time	Username	Problem	Language	Result	Execution time	Memory
334176		sebamarin	Aliens (IOI16_aliens)	C++14	4 / 100	7 ms	8704 KiB

aliens

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> ii;
#define db(x) cout<<#x<<" = "<<x<<"\n";
#define fore(i,a,b) for(ll i=a,ggdem=b;i<ggdem;i++)
#define FIN ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define SZ(a) ((ll)(a).size())
#define ALL(a) a.begin(),a.end()
#define mset(a,b) memset(a,b,sizeof(a));
#define pb push_back
#define fst first
#define snd second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const ll INF=1e15;
ll n,m,k,dp[1024][1024],wh[1024];
vector<ii>v;
ll sq(ll x){return x*x;}
bool in(ii a,ii b) { // a inside b
  return b.fst<=a.fst && a.snd<=b.snd;
}
ll cost(ll l,ll r,ll mid) { // [l,r] - [m,r]
  ll res=0;
  if (l<=mid && mid<=r)res=sq(r-l+1) - sq(r-mid+1);
  else res=sq(r-l+1);
  // cout<<"["<<l<<","<<r<<"] - ["<<mid<<","<<r<<"]: "<<res<<endl;
  return res;
}
bool compare(const ii &a,const ii &b) {
  return a.fst<b.fst || (a.fst==b.fst && a.snd>b.snd);
}
ll solve(int i,int j) {
  if(i==n)return 0;
  if(dp[i][j]!=-1)return dp[i][j];
  ll res=INF;
  if(j==k) {
    res=cost(v[i].fst,v[n-1].snd,v[n].fst)+solve(n,j);
  } else {
    ll to=-1;
    fore(k,i,n) {
      to=max(to,v[k].snd);
      // cout<<i<<" to "<<k<<" : "<<cost(v[i].fst,to,v[k+1].fst) + solve(k+1,j+1)<<" | "<<v[i].fst<<" "<<to<<" "<<v[k+1].fst<<endl;
      res=min(res,cost(v[i].fst,to,v[k+1].fst) + solve(k+1,j+1));
    }
  }
  return dp[i][j]=res;
}
vector<ii> get(vector<int> &r,vector<int> &c) {
  vector<ii>v;
  fore(i,0,SZ(r)){
    if(r[i]<=c[i])v.pb({r[i],c[i]});
    else v.pb({c[i],r[i]});
  }
  sort(ALL(v),compare);
  vector<ii>res;
  for(auto it:v) {
    if(!SZ(res) || !in(it,res.back()))res.pb(it);
  }
  return res;
}
ll take_photos(int _n,int _m,int _k,vector<int>r,vector<int> c) {
  n=_n,m=_m,k=_k;
  v=get(r,c);
  n=SZ(v);
  v.pb({INF,INF});
  // cout<<"v: "<<endl;for(auto it:v)cout<<it.fst<<" "<<it.snd<<endl;cout<<"n: "<<n<<endl;
  memset(dp,-1,sizeof(dp));
  return solve(0,0);
}
/*
int main() {FIN;
	int n,m,k;
	cin>>n>>m>>k;
	vector<int>r(n),c(n);
	fore(i,0,n)cin>>r[i]>>c[i];
	cout<<take_photos(n,m,k,r,c)<<"\n";
}
5 7 2
0 3
4 4
4 6
4 5
4 6
---> 25
2 5 2
1 4
4 1
---> 16
*/

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