제출 #773407

#제출 시각아이디문제언어결과실행 시간메모리
773407JomnoiAliens (IOI16_aliens)C++17
0 / 100
1 ms468 KiB
#include <bits/stdc++.h> #include "aliens.h" using namespace std; const int MAX_M = 505; const long long INF = 1e18 + 7; int N, M, K; int a[MAX_M][MAX_M]; long long dp[MAX_M][MAX_M][MAX_M]; 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++) a[r[i] + 1][c[i] + 1]++; for (int i = 1; i <= M; i++) { for (int j = 1; j <= M; j++) a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1]; } for (int i = 0; i <= K; i++) { for (int j = 0; j <= M; j++) { for (int n = 0; n <= N; n++) dp[i][n][j] = INF; } } for (int i = 0; i <= M; i++) dp[0][0][i] = 0; for (int i = 1; i <= K; i++) { for (int j = 1; j <= M; j++) { for (int n = 1; n <= N; n++) { dp[i][n][j] = INF; for (int k = j; k >= 1; k--) { int cost = a[j][j] - a[k - 1][j] - a[j][k - 1] + a[k - 1][k - 1]; if (cost == 0) continue; dp[i][n][j] = min(dp[i][n][j], dp[i - 1][n - cost][k - 1] + 1ll * (j - k + 1) * (j - k + 1)); } // cout << i << ' ' << n << ' ' << j << " : " << dp[i][n][j] << endl; } } } long long ans = INF; for (int i = 1; i <= K; i++) { for (int j = 1; j <= M; j++) ans = min(ans, dp[i][N][j]); } return ans; }
#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...