Submission #732226

#	Time	Username	Problem	Language	Result	Execution time	Memory
732226		vjudge1	Aliens (IOI16_aliens)	C++17	25 / 100	59 ms	2432 KiB

aliens

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
using pii=pair<int,int>;
using pli=pair<long long,int>;
const long long inf=1e12+9;
pii a[509];
long long dp[509][509];
int pos[509];
long long take_photos(int n,int m,int k,vector<int>r,vector<int>c){
for1(i,0,n-1){
a[i+1].fi=max(r[i],c[i]);
a[i+1].se=min(r[i],c[i]);
}
a[0]={-1,-1};
sort(a+1,a+1+n);
for1(i,1,n){
dp[i][0]=inf;
}
long long ans=inf;
for1(j,1,k){
for1(i,j,n){
dp[i][j]=inf;
int mx=a[i].fi,mn=a[i].se;
for2(l,i,j){
mx=max(mx,a[l].fi);
mn=min(mn,a[l].se);
if (mn>a[l-1].fi){
long long newval=dp[l-1][j-1]+1ll*(mx-mn+1)*(mx-mn+1);
if (dp[i][j]>newval){
    dp[i][j]=newval;
    pos[i]=l;
}
}
else if (mn<=a[l-1].se)continue;
else {
long long newval=dp[l-1][j-1]+1ll*(mx-mn+1)*(mx-mn+1)-1ll*(a[l-1].fi-mn+1)*(a[l-1].fi-mn+1);
if (dp[i][j]>newval){
    dp[i][j]=newval;
    pos[i]=l;
}
}
}
}
ans=min(ans,dp[n][j]);
//cout<<ans<<" "<<j<<" "<<dp[n][j]<<" "<<pos[n]<<'\n';
}
return ans;
}
/*signed main(){
    srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(".INP","r",stdin);
    //freopen(".OUT","w",stdout);
    int n,m,k;
    cin>>n>>m>>k;
    vector<int>r,c;
    r.resize(n);
    c.resize(n);
    for1(i,0,n-1)cin>>r[i];
    for1(i,0,n-1)cin>>c[i];
    long long ans=take_photos(n,m,k,r,c);
    cout<<ans;
}*/

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