제출 #654219

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
654219		jamezzz	Aliens (IOI16_aliens)	C++17	0 / 100	2 ms	340 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pf printf
#define pb push_back
#define ppb pop_back
#define ppf pop_front
#define INF 1023456789
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<pair<ll,ll>,int> line;
typedef pair<int,int> ii;

#define maxn 100005

int n,m,k,cnt[maxn];
ll dp[maxn];
deque<line> dq;
vector<ii> pts,tmp;

inline ll sq(ll x){
	return x*x;
}

inline ld poi(line a,line b){
	auto[m1,c1]=a.fi;
	auto[m2,c2]=b.fi;
	return (ld)(c1-c2)/(m2-m1);
}

int calc(ll cost){
	while(!dq.empty())dq.ppb();
	for(int i=1;i<n;++i){
		ll m=-2*(pts[i].fi-1);
		ll c=dp[i-1]+cost+sq(pts[i].fi-1)-sq(max(0,pts[i-1].se-pts[i].fi+1));
		line l={{m,c},i-1};
		while(sz(dq)>=2&&poi(dq[sz(dq)-1],l)<=poi(dq[sz(dq)-1],dq[sz(dq)-2]))dq.ppb();
		dq.pb(l);
		while(sz(dq)>=2&&poi(dq[0],dq[1])<=pts[i].se)dq.ppf();
		line o=dq[0];
		dp[i]=o.fi.fi*pts[i].se+o.fi.se+sq(pts[i].se);
		cnt[i]=cnt[o.se]+1;
	}
	return cnt[n-1];
}

ll take_photos(int _n,int _m,int _k,vi r,vi c){
	n=_n,m=_m,k=_k;
	for(int i=0;i<n;++i){
		if(r[i]>c[i])swap(r[i],c[i]);
		tmp.pb({r[i],c[i]});
	}
	sort(all(tmp));
	pts.pb({-1,-1});
	for(int i=0;i<n;++i){
		while(!pts.empty()&&pts.back().fi==tmp[i].fi&&pts.back().se<=tmp[i].se)pts.ppb();
		pts.pb(tmp[i]);
	}
	n=pts.size();
	ll lo=0,hi=1e12,mid,res;
	while(lo<=hi){
		mid=(lo+hi)>>1;
		if(calc(mid)<=k)res=mid,hi=mid-1;
		else lo=mid+1;
	}
	calc(res);
	return dp[n-1]-k*res;
}

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

aliens.cpp: In function 'll take_photos(int, int, int, vi, vi)':
aliens.cpp:73:18: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |  return dp[n-1]-k*res;
      |                 ~^~~~

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