Submission #1023080

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023080		parsadox2	Aliens (IOI16_aliens)	C++17	25 / 100	109 ms	4952 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;

const int N = 5e2 + 10;
const long long inf = 1e18;
long long dp[N][N];

long long tav(int x)
{
    if(x < 0)
        return 0;
    return 1LL * x * x;
}

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    vector <pair<int , int>> vec;
    for(int i = 0 ; i < n ; i++)
    {
        if(r[i] > c[i])
            swap(r[i] , c[i]);
        vec.push_back(make_pair(r[i] , c[i]));
    }
    sort(vec.begin() , vec.end());
    vector <pair<int ,int>> all;
    all.push_back(vec[0]);
    for(auto u : vec)
    {
        if(all.back().F == u.F)
        {
            all.pop_back();
            all.push_back(u);
            continue;
        }
        if(u.S > all.back().S)
            all.push_back(u);
    }
    n = all.size();
    for(int i = 0 ; i < n ; i++)
    {
        dp[i][1] = tav(all[i].S - all[0].F + 1);
        //cout << i << " " << 1 << " : " << dp[i][1] << endl;
    }
    for(int j = 2 ; j <= k ; j++)  for(int i = 0 ; i < n ; i++)
    {
        dp[i][j] = dp[i][j - 1];
        for(int x = 0 ; x < i ; x++)
            dp[i][j] = min(dp[i][j] , dp[x][j - 1] + tav(all[i].S - all[x + 1].F + 1) - tav(all[x].S - all[x + 1].F + 1));
        //cout << i << " " << j << " : " << dp[i][j] << endl;
    }
    return dp[n - 1][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