Submission #290217

#	Time	Username	Problem	Language	Result	Execution time	Memory
290217		shayan_p	Aliens (IOI16_aliens)	C++17	25 / 100	88 ms	4608 KiB

aliens

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

#define F first
#define S second
#define PB push_back
#define sz(s) (int(s.size()))
#define bit(n, k) (((n)>>(k)) & 1)

using namespace std;

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

const int maxn = 1e5 + 10, mod = 1e9 + 7;
const ll inf = 1e13 + 10, INF = 1e18;

pll dp[maxn];
int mn[maxn];

ll f(int ln){
    return 1ll * ln * ln;
}
pll solve(int n, ll c){
    for(int i = n-1; i >= 0; i--){
	if(mn[i] > i){
	    dp[i] = dp[i+1];
	    continue;
	}
	dp[i] = {inf, inf};
	for(int j = i; j < n; j++)
	    dp[i] = min(dp[i], (pll){ dp[j+1].F + f(j - mn[i] + 1) - f(i - mn[i]) + c, dp[j+1].S + 1 });
    }
    return dp[0];
}
ll take_photos(int m, int n, int k, vector<int> X, vector<int> Y){
    for(int i = 0; i <= n; i++){
	mn[i] = n + 10;
    }
    for(int i = 0; i < m; i++){
	if(X[i] > Y[i])
	    swap(X[i], Y[i]);
	mn[Y[i]] = min(mn[Y[i]], X[i]);
    }
    for(int i = n-1; i >= 0; i--){
	mn[i] = min(mn[i], mn[i+1]);
    }
    ll l = -1, r = inf;
    while(r-l > 1){
	ll mid = (l+r) >> 1;
	pll p = solve(n, mid);
	if(p.S > k)
	    l = mid;
	else
	    r = mid;
    }
    pll p = solve(n, r);
    return 1ll * p.F - 1ll * k * r;
}

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