Submission #392230

#	Time	Username	Problem	Language	Result	Execution time	Memory
392230		AugustinasJucas	Aliens (IOI16_aliens)	C++14	16 / 100	74 ms	2252 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
int reik[1001][1001] = {0};
void pad(int e, int s){
    if(e > s) swap(e, s);
    for(int i = e; i <= s; i++){
        for(int j = e; j <= s; j++){
            reik[i][j] = 1;
        }
    }
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    if(n == k){
        for(int i = 0; i < n; i++){
            pad(r[i], c[i]);
        }
        int ret = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < m; j++){
                ret += reik[i][j];
            }
        }
        
        return ret;
    }else{ // r_i = c_i visada
        vector<int> vec;
        for(int i = 0; i < n; i++){
            vec.push_back(r[i]);
        }
        sort(vec.begin(), vec.end());
        // padalinu i k grupiu, kad galu skirtumu kvadratu suma butu kuo mazesne!
        long long dp[n+1][k+1];
        long long inf = 1e18;
        for(int i = 0; i <= n; i++) for(int j = 0; j <= k; j++) dp[i][j] = inf;
        dp[0][1] = 0;
        for(int i = 0; i < n; i++) dp[i][1] = 1ll * (vec[i] - vec[0] + 1) * 1ll * (vec[i] - vec[0] + 1);
        long long ans = dp[n-1][1];
        
        for(int i = 1; i < n; i++){
            for(int j = 2; j <= k; j++){ // koks ats, jei sitas uzbagia pref[i] ir naudota is viso j grupiu
                for(int h = 0; h < i; h++){
                    dp[i][j] = min(dp[i][j], dp[h][j-1] + 1ll * (vec[i]-vec[h+1] + 1) * 1ll * (vec[i]-vec[h+1]+1));
                }
                if(i == n-1) ans = min(ans, dp[i][j]);
            }
        }
        return ans;
    }
}

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