Submission #592774

#	Time	Username	Problem	Language	Result	Execution time	Memory
592774		AlperenT	Aliens (IOI16_aliens)	C++17	16 / 100	64 ms	2308 KiB

aliens

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

using namespace std;

const long long INF = 2e18 + 5;

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    if(n <= 50 && m <= 100 && k == n){
        vector<vector<bool>> arr(m, vector<bool>(m, false));

        for(int x = 0; x < n; x++){
            for(int i = min(c[x], r[x]); i <= max(c[x], r[x]); i++){
                for(int j = min(c[x], r[x]); j <= max(c[x], r[x]); j++){
                    arr[i][j] = true;
                }
            }
        }

        int ans = 0;

        for(int i = 0; i < m; i++){
            for(int j = 0; j < m; j++){
                ans += arr[i][j];
            }
        }

        return ans;
    }
    else{
        vector<vector<long long>> dp(n + 5, vector<long long>(k + 5, INF));

        vector<int> v = {-1};

        for(auto x : r) v.push_back(x);

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

        dp[0][0] = 0;

        for(int r = 1; r <= n; r++){
            for(int l = r; l >= 1; l--){
                for(int i = 1; i <= k; i++){
                    dp[r][i] = min(dp[r][i], dp[l - 1][i - 1] + 1ll * (v[r] - v[l] + 1) * (v[r] - v[l] + 1));
                }
            }
        }

        return *min_element(dp[n].begin(), dp[n].end());
    }
}

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