Submission #605336

#	Time	Username	Problem	Language	Result	Execution time	Memory
605336		MohamedFaresNebili	Aliens (IOI16_aliens)	C++14	0 / 100	1 ms	212 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[505][505];

            long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
                N = n; M = m, K = k; memset(A, -1, sizeof A);
                for(ll l = 0; l < N; l++) {
                    if(c[l] < r[l]) swap(c[l], r[l]);
                    A[r[l]] = max(A[r[l]], ll(c[l]));
                }
                vector<pair<ll, ll>> C; C.push_back({0, 0});
                for(ll l = 0; l < M; l++) {
                    if(A[l] == -1) continue;
                    if(C.empty() || C.back().ss < A[l])
                        C.push_back({l + 1, A[l] + 1});
                }
                N = C.size() - 1;
                ll best = 2e18;
                for(ll l = 0; l <= N; l++)
                    for(ll i = 0; i <= K; i++)
                        DP[l][i] = 2e18;
                DP[0][0] = 0;
                for(ll l = 1; l <= K; l++) {
                    DP[0][l] = 0;
                    for(ll i = 1; i <= N; i++) {
                        for(ll j = 1; j <= i; j++) {
                            ll cur = C[i].ss - C[j].ff + 1; cur = max(cur, 0ll); cur *= cur;
                            ll rem = C[j - 1].ss - C[j].ff + 1; rem = max(rem, 0ll); rem *= rem;
                            DP[i][l] = min(DP[i][l], DP[j - 1][l - 1] + cur - rem);
                        }
                    }
                    best = min(best, DP[N][l]);
                }
                return best;
            }

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