Submission #1332231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1332231		activedeltorre	Aliens (IOI16_aliens)	C++20	4 / 100	1 ms	836 KiB

aliens

#include "aliens.h"

#include <cstdio>
#include <cassert>
#include <vector>
#include <iostream>
using namespace std;
int maxim[100005];
int maximpref[100005];
long long dp[10005][1005];
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    swap(n,m);
    for(int i=0;i<=n;i++)
    {
        maxim[i]=n+1;
        maximpref[i]=0;
    }
    for(int i=0;i<m;i++)
    {
        r[i]++;
        c[i]++;
        maxim[max(r[i],c[i])]=min(maxim[max(r[i],c[i])],min(r[i],c[i]));
        maximpref[min(r[i],c[i])]=max(maximpref[min(r[i],c[i])],max(r[i],c[i]));
    }
    for(int i=1;i<=n;i++)
    {
        maximpref[i]=max(maximpref[i],maximpref[i-1]);
        //cout<<maximpref[i]<<" ";
    }
    //cout<<'\n';
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=k;j++)
        {
            dp[i][j]=n*n;
            if(maxim[i]==n+1)
            {
                dp[i][j]=dp[i-1][j];
                continue;
            }
            if(j==0)
            {
                continue;
            }
            for(int lower=maxim[i];lower>=1;lower--)
            {
                int nxt=maximpref[lower-1];
                if(nxt<i)
                {
                    long long add;
                    if(nxt>=lower)
                    {
                        add=1ll*(nxt-lower+1)*(nxt-lower+1);
                    }
                    else
                    {
                        add=0;
                    }

                    dp[i][j]=min(dp[i][j],dp[nxt][k-1]+1ll*(i-lower+1)*(i-lower+1)-add);
                }
            }
        }
    }
    //cout<<dp[4][1]<<'\n';
    return dp[n][k];
}

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