제출 #173271

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
173271		dndhk	Aliens (IOI16_aliens)	C++14	4 / 100	2 ms	376 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 = 50000;

int N, M, K;
vector<pii> vt;
vector<ll> C;
ll dp[2][MAX_N+1];
bool sf(pii a, pii b){
	if(a.first==b.first){
		return a.second>b.second;
	}
	return a.first<b.first;
}

/*struct Lichao{
	struct NODE{
		int l, r;
		ll a, b;
	};
	ll SZ;
	vector<NODE> seg;
	void add(){
		seg.pb({-1, -1, 0, INFLL});
	}
	void Init(int x){
		SZ = (ll)x;
		add();
		init(0, 0LL, SZ);
	}
	void Reset(){
		for(int i=0; i<seg.size(); i++){
			seg[i].a = 0LL; seg[i].b = INFLL;
		}
	}
	void init(int idx, ll s, ll e){
		if(s==e)	return;
		seg[idx].l = seg.size(); add();
		seg[idx].r = seg.size(); add();
		init(seg[idx].l ,s, (s+e)/2); init(seg[idx].r, (s+e)/2+1, e);
	}
	void Update(ll a, ll b){
		update(0, 0LL, SZ, a, b);
	}
	void update(int idx, ll s, ll e, ll x, ll y){
		if(s*x+y<=seg[idx].a*s+seg[idx].b && e*x+y<=seg[idx].a*e+seg[idx].b){
			seg[idx].a = x;
			seg[idx].b = y;
			return;
		}else if(s*x+y>=seg[idx].a*s+seg[idx].b && e*x+y>=seg[idx].a*e+seg[idx].b){
			return;
		}
		update(seg[idx].l, s, (s+e)/2, x, y);
		update(seg[idx].r, (s+e)/2+1, e, x, y);
	}
	ll Calc(ll x){
		return calc(0, 0LL, SZ, x);
	}
	ll calc(int idx, ll s, ll e, ll k){
		if(s==e){
			return seg[idx].a * k + seg[idx].b;
		}
		if(k<=(s+e)/2){
			return min(seg[idx].a * k + seg[idx].b, calc(seg[idx].l, s, (s+e)/2, k));
		}else{
			return min(seg[idx].a * k + seg[idx].b, calc(seg[idx].r, (s+e)/2+1, e, k));
		}
	}
}Seg;*/

vector<pll> st;
int idx = 0;

void add(ll a, ll b){
	while(st.size()>=2){
		pll prv = st.back(); st.pop_back();
		if((b-prv.second) * (prv.first - st.back().first) <= (a-prv.first) * (prv.second - st.back().second)){
			continue;
		}else{
			st.pb(prv);
			break;
		}
	}
	st.pb({a, b});
}

ll calc(ll x){
	while(idx+1<vt.size()){
		if(st[idx+1].first * x + st[idx+1].second < st[idx].first * x + st[idx].second) idx++;
		else	break;
	}
	return st[idx].first * x + st[idx].second;
}

void solve(){
	dp[1][0] = 0LL;
	while(!st.empty())	st.pop_back();
	idx = 0;
	for(int i=0; i<vt.size(); i++){
		//Seg.Update(-2LL * vt[i].first, dp[0][i] - C[i] + (ll)vt[i].first * (ll)vt[i].first);
		add(-2LL * vt[i].first, dp[0][i] - C[i] + (ll)vt[i].first * (ll)vt[i].first);
		dp[1][i+1] = (ll)vt[i].second * (ll)vt[i].second + calc((ll)vt[i].second);
	}
}

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(), sf);
	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);
	}
	sort(vt.begin(), vt.end());
	while(!vt.empty() && vt.back().first==INF && vt.back().second==INF)	vt.pop_back();
	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;
	//Seg.Init(M);
	while(K--){
		solve();
		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()];
}

컴파일 시 표준 에러 (stderr) 메시지

aliens.cpp: In function 'll calc(ll)':
aliens.cpp:111:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(idx+1<vt.size()){
        ~~~~~^~~~~~~~~~
aliens.cpp: In function 'void solve()':
aliens.cpp:122:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<vt.size(); i++){
               ~^~~~~~~~~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:144:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<=vt.size(); i++){
               ~^~~~~~~~~~~
aliens.cpp:148:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<vt.size(); i++){
               ~^~~~~~~~~~
aliens.cpp:155:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<=vt.size(); i++){
                ~^~~~~~~~~~~

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