Submission #605154

#	Time	Username	Problem	Language	Result	Execution time	Memory
605154		MohamedFaresNebili	Aliens (IOI16_aliens)	C++14	16 / 100	94 ms	2288 KiB

aliens

#include <bits/stdc++.h>
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")
 
            using namespace std;
 
            using ll = long long;
            using ld = long double;
 
            #define ff first
            #define ss second
            #define pb push_back
            #define all(x) (x).begin(), (x).end()
            #define lb lower_bound
 
            const int MOD = 998244353;
 
            ll N, M, K, A[1001];
            ll DP[500][501];
            ll solve(ll i, ll t) {
                if(t < 0) return 1000000000LL * 1000000000LL;
                if(i == N) return 0;
                if(DP[i][t] != -1) return DP[i][t];
                ll best = 1000000000LL * 1000000000LL;
                for(ll l = i; l < N; l++) {
                    ll cur = (A[l] - A[i] + 1); cur *= cur;
                    best = min(best, cur + solve(l + 1, t - 1));
                }
                return DP[i][t] = best;
            }
 
            long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
                M = m, K = k;
                if(k <= 50 && k == n) {
                    ll res = 0;
                    for(int l = 0; l < K; l++) {
                        for(int i = min(r[l], c[l]); i <= max(r[l], c[l]); i++)
                            for(int j = min(r[l], c[l]); j <= max(r[l], c[l]); j++) {
                                res += 1 - DP[i][j];
                                DP[i][j] = 1;
                            }
                    }
                    return res;
                }
                sort(r.begin(), r.end());
              	memset(DP, -1, sizeof DP);
                for(auto u : r) {
                    if(N == 0 || A[N - 1] != u)
                        A[N++] = u;
                }
                ll best = solve(0, k);
                return best;
            }

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