제출 #962515

#제출 시각아이디문제언어결과실행 시간메모리
962515MinaRagy06Aliens (IOI16_aliens)C++17
12 / 100
141 ms2396 KiB
#include <bits/stdc++.h> #include "aliens.h" #ifdef MINA #include "grader.cpp" #endif using namespace std; #define ll long long #define sz(x) (int) x.size() ll take_photos(int n, int crap, int m, vector<int> R, vector<int> C) { array<ll, 2> a[n + 1]; vector<ll> v; for (int i = 1; i <= n; i++) { a[i] = {R[i - 1], C[i - 1]}; if (a[i][0] > a[i][1]) swap(a[i][0], a[i][1]); } sort(a + 1, a + n + 1); ll dp[m + 1][n + 1]; memset(dp, '?', sizeof dp); for (int j = 0; j <= m; j++) { dp[j][0] = 0; } for (int j = 1; j <= m; j++) { for (int i = 1; i <= n; i++) { ll mx = -1e18; for (int k = i; k >= 1; k--) { mx = max(mx, a[k][1]); ll c = (mx - a[k][0] + 1) * (mx - a[k][0] + 1); if (i + 1 <= n && mx >= a[i + 1][0]) { c -= (mx - a[i + 1][0] + 1) * (mx - a[i + 1][0] + 1); } dp[j][i] = min(dp[j][i], dp[j - 1][k - 1] + c); // cout << k << " to " << i << ": " << c << '\n'; } } } return dp[m][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...