Submission #172461

#	Time	Username	Problem	Language	Result	Execution time	Memory
172461		red1108	Aliens (IOI16_aliens)	C++17	41 / 100	542 ms	197240 KiB

aliens

#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false);cin.tie(0)
#define fopen freopen("input.txt", "r", stdin)
#define pb push_back
#define prec(a) cout<<fixed;cout.precision(a);
#define all(a) (a).begin(), (a).end()
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tiii;
const ll INF = 1e18;
const int inf = 2e9;
template<class T>
void pr(T t) {cout << t << " ";}
template<class T, class ...Args>
void pr(T a, Args ...args) {cout << a << " ";pr(args...);}
template<class ...Args>
void prl(Args ...args) {pr(args...);cout << endl;}

ll dp[5010][5010];
struct Line{
	vector<pll> l;
	int cur=0;
	double cross(pll a, pll b){
		return (double)(b.se-a.se)/(double)(a.fi-b.fi);
	}
	void add(ll a, ll b){
		//printf("add (%lld,%lld)\n", a,b);
		pll nl = pll(a,b);
		while(l.size()>=2&&cross(l[l.size()-2],l[l.size()-1])>=cross(l[l.size()-2],nl)) l.pop_back();
		l.push_back(nl);
		//for(auto i:l) printf("after add:(%lld,%lld)\n",i.fi,i.se);
	}
	ll get(ll x){
		while(cur+1<l.size()&&cross(l[cur],l[cur+1])<=(double)x) cur++;
		if(cur>=l.size()) return 0;
		return l[cur].fi*x+l[cur].se;
	}
}lines[5010];

ll take_photos(int n, int m, int k, vector<int>x, vector<int>y){
	k=min(n,k);
	vector<pll> tmp,p;
	for(int i=0;i<n;i++){
		if(x[i]>y[i]) swap(x[i], y[i]);
		tmp.pb({x[i],y[i]});
	}
	sort(tmp.begin(), tmp.end(), [](pii a, pii b){if(a.se==b.se) return a.fi>b.fi;return a.se<b.se;});
	p.pb({-1,-1});
	for(auto i:tmp){
		while(!p.empty()&&p[p.size()-1].fi>=i.fi) p.pop_back();
		p.pb(i);
	}
	lines[0].add(-2*(p[1].fi-1),(p[1].fi-1)*(p[1].fi-1));
	for(int i=1;i<(int)p.size();i++){
		//printf("i=%d----\n", i);
		for(int j=1;j<k;j++){
			if(p[i].fi<=p[i-1].se) lines[j].add(-2*(p[i].fi-1),dp[i-1][j]+(p[i].fi-1)*(p[i].fi-1) - (p[i-1].se-p[i].fi+1)*(p[i-1].se-p[i].fi+1));
			else lines[j].add(-2*(p[i].fi-1),dp[i-1][j]+(p[i].fi-1)*(p[i].fi-1));
		}
		for(int j=1;j<=k;j++){
			dp[i][j]=lines[j-1].get(p[i].se)+p[i].se*p[i].se;
			//printf("debug[%d][%d]=%lld\n", i,j,dp[i][j]);
		}
	}
	return dp[p.size()-1][k];
}

Compilation message (stderr)

aliens.cpp: In member function 'll Line::get(ll)':
aliens.cpp:41:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(cur+1<l.size()&&cross(l[cur],l[cur+1])<=(double)x) cur++;
         ~~~~~^~~~~~~~~
aliens.cpp:42:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(cur>=l.size()) return 0;
      ~~~^~~~~~~~~~

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