제출 #961341

#제출 시각아이디문제언어결과실행 시간메모리
961341MinaRagy06Aliens (IOI16_aliens)C++17
12 / 100
117 ms2424 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]; vector<ll> v; for (int i = 0; i < n; i++) { a[i] = {r[i], c[i]}; v.push_back(r[i]); v.push_back(c[i]); } v.push_back(-1); sort(v.begin(), v.end()); v.resize(unique(v.begin(), v.end()) - v.begin()); auto get = [&] (int x) { return lower_bound(v.begin(), v.end(), x) - v.begin(); }; n = v.size() - 1; ll mn[n + 1]{}, mx[n + 1]{}; for (int i = 0; i <= n; i++) { mn[i] = 1e9; mx[i] = -1e9; } for (int i = 0; i < sz(r); i++) { a[i][0] = get(a[i][0]); a[i][1] = get(a[i][1]); mn[a[i][0]] = min(mn[a[i][0]], a[i][1]); mx[a[i][0]] = max(mx[a[i][0]], a[i][1]); // cout << "> " << a[i][0] << ' ' << a[i][1] << '\n'; } 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 curmn = 1e9, curmx = -1e9; for (int k = i; k >= 1; k--) { curmn = min(curmn, mn[k]); curmx = max(curmx, mx[k]); // if (j == m && i == n && k == 3) { // cout << "HI" << endl; // } if (k <= curmn && curmx <= i) { dp[j][i] = min(dp[j][i], dp[j - 1][k - 1] + (v[i] - v[k] + 1) * (v[i] - v[k] + 1)); } } } } // cout << dp[1][2] << '\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...