Submission #69209

#	Time	Username	Problem	Language	Result	Execution time	Memory
69209		mr_banana	Aliens (IOI16_aliens)	C++17	12 / 100	477 ms	2724 KiB

aliens

#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
const int MN=500+10;
long long inf;
long long dp[MN][MN];
pair<int,int> p[MN];
long long sq(int x){
    return 1ll*x*x;
}
bool g[MN][MN];
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    inf=1ll*m*m;
    for(int i=0;i<n;i++){
        p[i]={min(r[i],c[i]),-max(r[i],c[i])-1};
    }
    sort(p,p+n);
    int n1=unique(p,p+n)-p;
    n=0;
    int mx=-1;
    for(int i=0;i<n1;i++){
        if(mx<-p[i].second){
            p[n++]={p[i].first,-p[i].second};
            mx=p[i].second;
        }
    }
    /*long long ans=0;
    for(int i=0;i<n;i++){
        for(int j=p[i].first;j<p[i].second;j++){
            for(int k=p[i].first;k<p[i].second;k++){
                if(g[j][k]==0){
                    g[j][k]=1;
                    ans++;
                }
            }
        }
    }
    */
    for(int i=0;i<n;i++){
        for(int j=0;j<=k;j++){
            dp[i+1][j]=inf;
            for(int l=0;l<=i;l++){
                if(j){
                    if(l==0){
                        dp[i+1][j]=min(dp[i+1][j],sq(p[i].second-p[l].first)+dp[l][j-1]);
                    }
                    else{
                        dp[i+1][j]=min(dp[i+1][j],dp[l][j-1]+sq(p[i].second-p[l].first)-sq(max(0,p[l-1].second-p[l].first)));
                    }
                }
            }

        }
    }
    return dp[n][k];
}

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