Submission #1284961

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284961		Martincho506	Aliens (IOI16_aliens)	C++20	41 / 100	286 ms	151368 KiB

aliens

#include<iostream>
#include<vector>
#include<algorithm>
#include<assert.h>
using namespace std;

const long long MAXN = 1e4+7;
const long long INF = 1e18;
pair<long long, long long> tt[MAXN];
vector<pair<long long, long long> > a;
long long dp[MAXN][MAXN], opt[MAXN][MAXN], n, m;

bool cmp(pair<long long, long long> a1, pair<long long, long long> b1)
{
    if(a1.first < b1.first) return true;
    if(a1.first > b1.first) return false;
    if(a1.second > b1.second) return true;
    return false;
}

long long take_photos(int nn, int mm, int k, vector<int> r, vector<int> c)
{
    n = nn;
    m = mm;
    for(long long i = 1; i <= n; i++)
    {
        tt[i].first = min(c[i-1], r[i-1]);
        tt[i].second = max(c[i-1], r[i-1]);
    }
    sort(tt+1, tt+n+1, cmp);
    long long maxi = -1;
    for(long long i = 1; i <= n; i++)
    {
        if(tt[i].second > maxi)
        {
            maxi = tt[i].second;
            a.push_back(tt[i]);
        }
    }
    for(long long i = 0; i < a.size(); i++)
    {
        dp[i][1] = (a[i].second-a[0].first+1)*(a[i].second-a[0].first+1);
        opt[i][1] = 0;
    }
    for(long long i = 1; i <= k; i++)
    {
        //dp[a.size()][i] = (a[0].second-a[0].first+1)*(a[0].second-a[0].first+1);
        opt[a.size()][i] = a.size()-1;
    }
    for(long long i = 2; i <= k; i++)
    {
        for(long long j = a.size()-1; j >= 0; j--)
        {
            long long mini = INF, minii = -1;
            for(long long jj = opt[j][i-1]; jj <= opt[j+1][i]; jj++)
            {
                long long ss = max(0LL, a[jj].second-a[jj+1].first+1);
                if(dp[jj][i-1]+(a[j].second-a[jj+1].first+1)*(a[j].second-a[jj+1].first+1)-ss*ss < mini)
                {
                    mini = dp[jj][i-1]+(a[j].second-a[jj+1].first+1)*(a[j].second-a[jj+1].first+1)-ss*ss;
                    minii = jj;
                }
            }
            opt[j][i] = minii;
            dp[j][i] = mini;
        }
    }
    long long sz = a.size()-1;
    return dp[sz][k];
}

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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