Submission #173255

#	Time	Username	Problem	Language	Result	Execution time	Memory
173255		dndhk	Aliens (IOI16_aliens)	C++14	12 / 100	113 ms	388 KiB

aliens

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

#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 0
#define TEST if(test)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1e15;
const int MAX_N = 4000;

int N, M, K;
vector<pii> vt;
vector<ll> C;
ll dp[2][MAX_N+1];

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
	N = n; M = m; K = k;
	for(int i=0; i<N; i++){
		vt.pb({min(r[i], c[i]), max(r[i], c[i]) + 1});
	}
	sort(vt.begin(), vt.end());
	int mx = -1;
	for(int i=0 ;i<N; i++){
		if(mx>=vt[i].second){
			vt[i].second = INF;
			vt[i].first = INF;
		}else mx = max(mx, vt[i].second);
	}
	mx = M+1;
	for(int i=N-1; i>=0; i--){
		if(vt[i].first==INF && vt[i].second==INF)	continue;
		if(mx<=vt[i].first){
			vt[i].first = INF;
			vt[i].second = INF;
		}else mx = min(mx, vt[i].first);
	}
	sort(vt.begin(), vt.end());
	while(!vt.empty() && vt.back().first==INF && vt.back().second==INF)	vt.pop_back();
	TEST{
		for(int i=0; i<vt.size(); i++){
			cout<<vt[i].first<<" "<<vt[i].second<<endl;
		}
	}
	for(int i=0; i<=vt.size(); i++){
		dp[0][i] = dp[1][i] = INFLL;
	}
	C.pb(0LL);
	for(int i=1; i<vt.size(); i++){
		C.pb(max(0LL, (ll)(vt[i-1].second - vt[i].first)) * max(0LL, (ll)(vt[i-1].second - vt[i].first)));
	}
	dp[0][0] = dp[1][0] = 0LL;
	while(K--){
		dp[1][0] = 0LL;
		for(int i=0; i<vt.size(); i++){
			for(int j=0; j<=i; j++){
				dp[1][i+1] = min(dp[1][i+1], dp[0][j] + (ll)(vt[i].second - vt[j].first) * (ll)(vt[i].second - vt[j].first) + C[j]);
			}
		}
		for(int i=0; i<=vt.size(); i++){
			TEST cout<<dp[1][i]<<" ";
			dp[0][i] = dp[1][i];
			dp[1][i] = INFLL;
		}
		TEST cout<<endl;
	}
	return dp[0][vt.size()];
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:57:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<vt.size(); i++){
                ~^~~~~~~~~~
aliens.cpp:61:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<=vt.size(); i++){
               ~^~~~~~~~~~~
aliens.cpp:65:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<vt.size(); i++){
               ~^~~~~~~~~~
aliens.cpp:71:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<vt.size(); i++){
                ~^~~~~~~~~~
aliens.cpp:76:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<=vt.size(); i++){
                ~^~~~~~~~~~~

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