Submission #605152

#	Time	Username	Problem	Language	Result	Execution time	Memory
605152		MohamedFaresNebili	Aliens (IOI16_aliens)	C++14	4 / 100	51 ms	2272 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 == 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: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40