Submission #22946

#TimeUsernameProblemLanguageResultExecution timeMemory
22946sampritiAliens (IOI16_aliens)C++14
0 / 100
0 ms7792 KiB
#include "aliens.h" #include <vector> #include <algorithm> #include <climits> using namespace std; int N, M, K; vector<long long> R, C; int R_map[1000000]; long long dp[500][500]; long long solve(int i, int j) { if(i == N) return 0; if(j == K && i < N) return LLONG_MAX/2; if(dp[i][j] != -1) return dp[i][j]; dp[i][j] = LLONG_MAX/2; for(int k = i; k < N; k++) { long long width = max(C[i], R[k]) - R[i] + 1; dp[i][j] = min(dp[i][j], width * width + solve(k + 1, j + 1)); } return dp[i][j]; } long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { N = n, M = m, K = k; for(int i = 0; i < N; i++) { if(c[i] < r[i]) { int t = r[i]; r[i] -= (t - c[i]); c[i] = t; } } for(int i = 0; i < M; i++) R_map[i] = -1; for(int i = 0; i < N; i++) { R_map[r[i]] = max(R_map[r[i]], c[i]); } int cover = -1; for(int i = 0; i < M; i++) { if(R_map[i] == -1 || R_map[i] - i <= cover) { R_map[i] = -1; } else cover = R_map[i]; cover--; } cover = -1; for(int i = M - 1; i >= 0; i--) { if(R_map[i] == -1 || R_map[i] - i <= cover) { R_map[i] = -1; } else cover = R_map[i]; cover--; } for(int i = 0; i < M; i++) { if(R_map[i] == -1) continue; R.push_back(i); C.push_back(R_map[i]); } N = R.size(); for(int i = 0; i < N; i++) { for(int j = 0; j < K; j++) { dp[i][j] = -1; } } return solve(0, 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...