Submission #853531

#	Time	Username	Problem	Language	Result	Execution time	Memory
853531		abcvuitunggio	Aliens (IOI16_aliens)	C++17	25 / 100	93 ms	23768 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF=1e18;
int n,dp[501][501],s[100001],e[100001],mx[1000001];
vector <pair <int, int>> ve;
int f(int i, int j){
    if (j<0)
        return INF;
    if (i==n)
        return 0;
    if (dp[i][j]!=-1)
        return dp[i][j];
    dp[i][j]=INF;
    for (int k=i;k<n;k++){
        int cost=(e[k]-s[i]+1)*(e[k]-s[i]+1);
        if (s[k+1]<=e[k])
            cost-=(e[k]-s[k+1]+1)*(e[k]-s[k+1]+1);
        dp[i][j]=min(dp[i][j],f(k+1,j-1)+cost);
    }
    return dp[i][j];
}
long long take_photos(int32_t N, int32_t M, int32_t K, vector <int32_t> R, vector <int32_t> C){
    memset(mx,-1,sizeof(mx));
    memset(dp,-1,sizeof(dp));
    for (int i=0;i<N;i++)
        mx[min(R[i],C[i])]=max(mx[min(R[i],C[i])],(int)max(R[i],C[i]));
    for (int i=0;i<M;i++)
        if (mx[i]!=-1)
            ve.emplace_back(i,mx[i]);
    sort(ve.begin(),ve.end());
    int cur=-1;
    for (auto [i,j]:ve)
        if (j>cur){
            s[n]=i;
            e[n]=j;
            n++;
            cur=j;
        }
    s[n]=INF;
    return f(0,K);
}

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