Submission #284592

#TimeUsernameProblemLanguageResultExecution timeMemory
284592A02Aliens (IOI16_aliens)C++14
4 / 100
1 ms256 KiB
#include <vector> #include <string> #include <set> #include <algorithm> #include <iostream> #include <utility> #include "aliens.h" using namespace std; long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { if (k == n && m <= 100){ int total = 0; for (int i = 0; i < m; i++){ for (int j = 0; j < m; j++){ bool good = false; for (int a = 0; a < n; a++){ if (i <= max(r[a], c[a]) && j <= max(r[a], c[a]) && i >= min(r[a], c[a]) && j >= min(r[a], c[a])){ good = true; } } if (good){ total++; } } } return total; } bool is_central = true; for (int i = 0; i < n; i++){ if (r[i] != c[i]){ is_central = false; } } if (is_central && n <= 500 && m <= 100){ vector<int> locations; for (int i = 0; i < n; i++){ if (find(locations.begin(), locations.end(), r[i]) == locations.end()){ locations.push_back(r[i]); } } sort(locations.begin(), locations.end()); n = locations.size(); vector<vector<int> > DPnk (n, vector<int> (k + 1, m * m)); for (int N = 0; N < n; N++){ for (int K = 1; K <= k; K++){ DPnk[N][K] = (locations[N] - locations[0] + 1) * (locations[N] - locations[0] + 1); for (int n1 = 1; n1 <= N; n1++){ DPnk[N][K] = min(DPnk[N][K], DPnk[n1 - 1][K - 1] + (locations[N] - locations[n1] + 1) * (locations[N] - locations[n1] + 1)); } } } return DPnk[n - 1][k]; } return 0; }
#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...