Submission #635664

#	Time	Username	Problem	Language	Result	Execution time	Memory
635664		ionan6ix	Aliens (IOI16_aliens)	C++17	25 / 100	120 ms	1236 KiB

aliens

#include "aliens.h"
#include<bits/stdc++.h>

using namespace std;

bool cmp(pair<int,int> a,pair<int,int> b)
{
    if(a.first==b.first)
        return a.second>b.second;

    return a.first<b.first;
}

bool inters(pair<int,int> a,pair<int,int> b)
{
    if(a.first<=b.first && a.second>=b.second)
        return true;
    return false;
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {

    if(n<=50 && m<=100 && k==n) //First Subtask
    {
        int sol = 0;
        vector<vector<int> > matrix;

        matrix.resize(m);

        for(int i = 0;i<m;i++)
            matrix[i].resize(m);

        for(int i=0;i<m;i++)
            for(int j=0;j<m;j++)
                matrix[i][j] = 0;

        for(int i = 0;i<n;i++)
        {
            if(matrix[r[i]][c[i]]) continue;

            int m = min(r[i],c[i]);
            int M = max(r[i],c[i]);
            for(int j = m;j<=M;j++)
                for(int t = m;t<=M;t++)
                    matrix[j][t] = 1;

        }

        for(int i = 0;i<m;i++)
            for(int j=0;j<m;j++)
                sol+=matrix[i][j];

        return sol;
    }
    bool flag = true;

    for(int i = 0;i<n;i++)
        if(r[i]!=c[i])
        {
            flag = false;
            break;
        }

    if(n<=500 && m<=1000 && flag)
    {
        vector<pair<int,int> > obj;
        for(int i = 0;i<n;i++)
            obj.emplace_back(r[i],c[i]);

        sort(obj.begin(),obj.end());

        vector<vector<int> > dp;
        dp.resize(n+1);
        for(int i=0;i<=n;i++)
        {
            dp[i].resize(k+1);
            for(int j=0;j<=k;j++)
                dp[i][j] = 1000000000;
        }
        dp[0][0] = 0;


        for(int i = 0;i<n;i++)
        {
            for(int j = 0;j<=i;j++) {
                for (int t = 1; t <= k; t++) {
                    int area = (obj[i].first - obj[j].first + 1) * (obj[i].second - obj[j].second + 1);



                    dp[i+1][t] = min(dp[i+1][t], dp[j][t-1] + area);

                }
            }
        }

        int sol = INT_MAX;
        for(int j=1;j<=k;j++)
            sol=min(sol,dp[n][j]);
        return sol;
    }
        else
    if(n<=500 && m<=1000)
    {
        vector<pair<int,int> > obj;
        vector<pair<int,int> > aux;


        for(int i = 0;i<n;i++)
            aux.emplace_back(min(r[i],c[i]),max(r[i],c[i]));

        sort(aux.begin(),aux.end(),cmp);


        obj.emplace_back(-1,-1);

        for(auto it:aux)
        {
            if(!inters(obj.back(),it))
                obj.push_back(it);
        }

        n = obj.size();
        vector<vector<int> > dp;
        dp.resize(n+1);
        for(int i=0;i<=n;i++)
        {
            dp[i].resize(k+1);
            for(int j=0;j<=k;j++)
                dp[i][j] = 1000000000;
        }
        dp[0][0] = 0;

        for(int i = 1;i<n;i++)
        {
            for(int j = 1;j<=i;j++)
            {
                for(int t=1;t<=k;t++)
                {
                    dp[i][t] = min(dp[i][t],dp[j-1][t-1] + (obj[i].second-obj[j].first+1)*(obj[i].second-obj[j].first+1) - max(0,obj[j-1].second-obj[j].first+1)*max(0,obj[j-1].second-obj[j].first+1));

                }
            }
        }

        int sol = INT_MAX;
        for(int j=1;j<=k;j++)
            sol=min(sol,dp[n-1][j]);
        return sol;
    }
    return 0;
}

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