제출 #288546

#제출 시각아이디문제언어결과실행 시간메모리
288546arayiAliens (IOI16_aliens)C++17
0 / 100
1 ms768 KiB
#include <bits/stdc++.h> #include "aliens.h" #define lli long long int using namespace std; const int N = 1111; lli dp[N][N], mx[N]; long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) { for (int i = 0; i < n; i++) { mx[max(r[i], c[i]) + 1] = max(abs(r[i] - c[i]) + 1LL, mx[max(r[i], c[i]) + 1]); } for (int i = 1; i <= m; i++) { dp[i][0] = m * m; for (int j = 1; j <= k; j++) { lli mxx = mx[i]; dp[i][j] = i * i; int i1 = i; while(i1 > 0) { while(i1 > 1 && mx[i1 - 1] + i - i1 + 1 < mxx) i1--; i1--; dp[i][j] = min(dp[i][j], dp[i1][j - 1] + mxx * mxx - max(0LL, (mxx - i + i1)) * max(0LL, (mxx - i + i1))); mxx = mx[i1] + i - i1; } //cout << dp[i][j] << " "; } //cout << endl; } return dp[m][k]; }
#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...