제출 #569851

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
569851		CSQ31	Aliens (IOI16_aliens)	C++17	60 / 100	2096 ms	355800 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
vector<ll>dp[100001];
const ll INF = 1e18;
vector<int>b,h;
void solve(int lvl,int l,int r,int L,int R){
	//cout<<lvl<<" "<<l<<" "<<r<<" "<<L<<" "<<R<<'\n';
	int id = l;
	ll best = INF;
	int mid = (L+R)/2;
	//cout<<mid<<'\n';
	for(int i=l;i<=min(r,mid-1);i++){
		ll cost = b[mid] - h[b[i+1]]+1;
		cost*=cost;
		if(i && b[i] >= h[b[i+1]]){
			ll a = b[i] - h[b[i+1]]+1;
			cost-=a*a;
		}
		cost+=dp[i][lvl-1];
		if(best > cost){
			best = cost;
			id = i;
		}
	}
	dp[mid][lvl] = best;
	if(mid-1>=L)solve(lvl,l,id,L,mid-1);
	if(mid+1<=R)solve(lvl,id,r,mid+1,R);
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
	h.assign(m,m);
    for(int i=0;i<n;i++){
		int a = max(r[i],c[i]);
		int b = min(r[i],c[i]);
		h[a] = min(h[a],b);
	}
	int L = m;
	for(int i=m-1;i>=0;i--){
		if(h[i]==m)continue;
		if(h[i]<L)b.push_back(i);
		L = min(L,h[i]);	
	}
	b.push_back(-1);
	reverse(b.begin(),b.end());
	n = b.size()-1;
	//for(int x:b)cout<<x<<" ";
	//cout<<'\n';
	//for(int i=1;i<=n;i++)cout<<h[b[i]]<<" ";
	//cout<<'\n';
	for(int i=0;i<=n;i++){
		dp[i].assign(k+1,INF);
	}
	dp[0][0] = 0;
	for(int i=1;i<=k;i++){
		solve(i,0,n-1,1,n);
	}
	ll ans = INF;
	for(int i=1;i<=k;i++){
		ans = min(ans,dp[n][i]);
	}
	return ans;
}

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