제출 #962519

#제출 시각아이디문제언어결과실행 시간메모리
962519MinaRagy06Aliens (IOI16_aliens)C++17
25 / 100
2075 ms6748 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; } ll prf[n + 1]{}; prf[0] = -1e18; for (int i = 1; i <= n; i++) { prf[i] = max(prf[i - 1], a[i][1]); } 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 (prf[k - 1] >= a[k][0]) { c -= (prf[k - 1] - a[k][0] + 1) * (prf[k - 1] - a[k][0] + 1); } // cout << k << " to " << i << ": " << c << '\n'; if (c < 0) continue; dp[j][i] = min(dp[j][i], dp[j - 1][k - 1] + c); } } } 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...