제출 #140676

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
140676		Sorting	Aliens (IOI16_aliens)	C++14	25 / 100	147 ms	3960 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 5e2 + 7;
const int K = N;
const long long inf = 1e18;

bool cmp(pair<long long, long long> lvalue, pair<long long, long long> rvalue){
	if(lvalue.first != rvalue.first){
		return lvalue.first < rvalue.first;
	} 

	return lvalue.second > rvalue.second;
}

pair<long long, long long> p[N];
pair<long long, bool> dp[N][K];

long long solve(int pos, int left){
	if(left < 0){
		return inf;
	}
	if(pos < 0){
		return 0;
	}
	if(left == 0){
		return inf;
	}

	if(dp[pos][left].second){
		return dp[pos][left].first;
	}

	dp[pos][left].second = true;
	dp[pos][left].first = inf;

	for(int i = pos; i >= 0; i--){
		long long curr = solve(i - 1, left - 1);
		curr += (p[pos].second - p[i].first + 1ll) * (p[pos].second - p[i].first + 1ll);

		dp[pos][left].first = min(dp[pos][left].first, curr);
	}

	if(p[pos].second >= p[pos + 1].first){
		dp[pos][left].first -= (p[pos].second - p[pos + 1].first + 1ll) * (p[pos].second - p[pos + 1].first + 1ll);
	}

	return dp[pos][left].first;
}

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    for(int i = 0; i < n; i++){
    	if(r[i] > c[i]){
    		swap(r[i], c[i]);
    	}
    	p[i].first = r[i];
    	p[i].second = c[i];
    }

    sort(p, p + n, cmp);

    int mx = -1, j = 0;

    for(int i = 0; i < n; i++){
    	if(p[i].second <= mx){
    		continue;
    	}
    	//cout << p[i].first << " p[i] " << p[i].second << endl;
    	mx = p[i].second;
    	p[j] = p[i];
    	j++;
    }
    n = j;
    p[n].first = inf;

    return solve(n - 1, k);
}
/*
5 7 2
0 3
4 4
4 6
4 5
4 6
*/

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