| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 172332 | red1108 | Aliens (IOI16_aliens) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 = 9e18;
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[510][510];
ll f(int n, int m, int k, vector<int>x, vector<int>y){
vector<pii> tmp,pos;
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;});
for(auto i:tmp){
while(!pos.empty()&&pos[pos.size()-1].fi>=i.fi) pos.pop_back();
pos.pb(i);
}
dp[0][0]=INF;
dp[0][1]=(pos[0].se-pos[0].fi+1)*(pos[0].se-pos[0].fi+1);
for(int i=1;i<(int)pos.size();i++){
dp[i][0]=INF;
for(int j=1;j<=k;j++){
dp[i][j]=dp[i][j-1];
for(int ii=0;ii<=i;ii++){
if(ii==0) dp[i][j]=min(dp[i][j],(ll)(pos[i].se-pos[ii].fi+1)*(pos[i].se-pos[ii].fi+1));
else dp[i][j]=min(dp[i][j],dp[ii-1][j-1]+(pos[i].se-pos[ii].fi+1)*(pos[i].se-pos[ii].fi+1)-(pos[i].fi<=pos[ii-1].se?(ll)(pos[ii].fi-pos[ii-1].se+1)*(pos[ii].fi-pos[ii-1].se+1):0));
}
}
}
return dp[pos.size()-1][k];
}