Submission #605353

#	Time	Username	Problem	Language	Result	Execution time	Memory
605353		MohamedFaresNebili	Aliens (IOI16_aliens)	C++14	25 / 100	218 ms	4252 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;

            int A[1005], X[1005], Y[1005];
            ll DP[1005][1005];

            ll solve(ll x, ll y) {
                if(x > y) return 0;
                return (y - x + 1) * (y - x + 1);
            }
            ll calc(ll a, ll b, ll c, ll d) {
                a = max(a, c); c = min(b, d);
                return solve(a, c);
            }

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

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