제출 #348486

#제출 시각아이디문제언어결과실행 시간메모리
348486milleniumEeeeAliens (IOI16_aliens)C++17
25 / 100
147 ms2540 KiB
#include "aliens.h" //#include "grader.cpp" #include <bits/stdc++.h> #define y1 asdfasdf123 #define ll long long #define szof(s) (int)s.size() #define all(s) s.begin(), s.end() #define pii pair<int, int> #define fr first #define sc second using namespace std; const int INF = 0x3f3f3f3f; const int MAXN = 505; const int MAXM = 1005; bool used[155][155]; ll dp[MAXN][MAXN]; int r[MAXN]; int c[MAXN]; int n, m, k; int S(int x) { return x * x; } void f(int y1, int x1, int y2, int x2) { for (int i = y1; i <= y2; i++) { for (int j = x1; j <= x2; j++) { used[i][j] = true; } } } int subtask1() { for (int i = 1; i <= n; i++) { int mn = min(r[i], c[i]); int mx = max(r[i], c[i]); f(mn, mn, mx, mx); } long long ans = 0; for (int i = 1; i <= m; i++) { for (int j = 1; j <= m; j++) { if (used[i][j]) { ans++; } } } return ans; } /* 1 2 1 0 1 */ int cost(int left, int right) { return S(c[right] - r[left] + 1) - (left - 1 > 0 ? S(max(0, c[left - 1] - r[left] + 1)) : 0); } long long take_photos(int N, int M, int K, vector<int> R, vector<int> C) { n = N, m = M, k = K; for (int i = 0; i < n; i++) { r[i + 1] = R[i] + 1; c[i + 1] = C[i] + 1; } if (n <= 50 && m <= 100 && k == n) { return subtask1(); } for (int i = 1; i <= n; i++) { if (r[i] > c[i]) { swap(r[i], c[i]); } } // r[i] <= c[i]; set <pii> st; for (int i = 1; i <= n; i++) { st.insert({r[i], c[i]}); } n = szof(st); auto it = st.begin(); pii arr[MAXN]; for (int i = 1; i <= n; i++) { pii para = *it; r[i] = para.first; c[i] = para.second; it++; arr[i] = para; } sort(arr + 1, arr + n + 1, [&](pii a, pii b) { if (a.sc != b.sc) { return a.sc < b.sc; } else { return a.fr > b.fr; } }); vector <bool> used(n + 1, true); vector <int> suf_r(n + 1); suf_r[n] = arr[n].fr; for (int i = n - 1; i >= 1; i--) { suf_r[i] = min(arr[i].fr, suf_r[i + 1]); } vector <pii> nw; for (int i = 1; i < n; i++) { if (suf_r[i + 1] <= arr[i].fr) { used[i] = false; } else { nw.push_back(arr[i]); } } nw.push_back(arr[n]); n = szof(nw); for (int i = 0; i < n; i++) { arr[i + 1] = nw[i]; r[i + 1] = nw[i].fr; c[i + 1] = nw[i].sc; } // a[i] не внутри a[j] i != j k = min(k, n); memset(dp, INF, sizeof(dp)); dp[0][0] = 0; for (int gr = 1; gr <= k; gr++) { for (int i = 1; i <= n; i++) { for (int lst = 0; lst < i; lst++) { dp[gr][i] = min(dp[gr][i], dp[gr - 1][lst] + cost(lst + 1, i)); } } } return dp[k][n]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...