Submission #605454

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

            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] = C[l].ff + 1,
                    Y[l] = 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 = 0; j < i; j++) {
                            ll cur = DP[j][l - 1] + (Y[i - 1] - X[j] + 1) * (Y[i - 1] - X[j] + 1);
                            if(j > 0 && Y[j - 1] >= X[j])
                                cur -= (Y[j - 1] - X[j] + 1) * (Y[j - 1] - X[j] + 1);
                            DP[i][l] = min(DP[i][l], cur);
                        }
                    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