Submission #288546

#	Time	Username	Problem	Language	Result	Execution time	Memory
288546		arayi	Aliens (IOI16_aliens)	C++17	0 / 100	1 ms	768 KiB

aliens

#include <bits/stdc++.h>
#include "aliens.h"
#define lli long long int
using namespace std;

const int N = 1111;

lli dp[N][N], mx[N];
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c)
{
    for (int i = 0; i < n; i++)
    {
        mx[max(r[i], c[i]) + 1] = max(abs(r[i] - c[i]) + 1LL, mx[max(r[i], c[i]) + 1]);
    }
    for (int i = 1; i <= m; i++)
    {
        dp[i][0] = m * m;
        for (int j = 1; j <= k; j++)
        {
            lli mxx = mx[i];
            dp[i][j] = i * i;
            int i1 = i;
            while(i1 > 0)
            {
                while(i1 > 1 && mx[i1 - 1] + i - i1 + 1 < mxx) i1--;
                i1--;
                dp[i][j] = min(dp[i][j], dp[i1][j - 1] + mxx * mxx - max(0LL, (mxx - i + i1)) * max(0LL, (mxx - i + i1)));
                mxx = mx[i1] + i - i1;
            }
            //cout << dp[i][j] << " ";
        }
        //cout << endl;
    }
    return dp[m][k];
}

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