Submission #962401

#TimeUsernameProblemLanguageResultExecution timeMemory
962401RaresFelixAliens (IOI16_aliens)C++17
12 / 100
127 ms2644 KiB
#include <bits/stdc++.h> #include "aliens.h" //#pragma GCC optimize("O3") //#pragma GCC target("avx,avx2,fma") #define sz(x) int((x).size()) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() using namespace std; using ll = long long; using ld = long double; // or double, if TL is tight using str = string; using ii = pair<int, int>; using pl = pair<ll, ll>; using vi = vector<int>; using vll = vector<ll>; ll take_photos(int n0, int m, int k, vi r, vi c) { vector<ii> SegInit; for(int i = 0; i < n0; ++i) { SegInit.push_back({min(r[i], c[i]), max(r[i], c[i]) + 1}); } sort(all(SegInit), [&](auto a, auto b) { if(a.first != b.first) return a < b; return a > b; }); vector<ii> Seg; int cur_dr = -1; for(auto [st, dr] : SegInit) { if(dr <= cur_dr) continue; else { Seg.push_back({st, dr}); cur_dr = dr; } } int n = Seg.size(); vll st(n, 0), dr(n, 0), sb(n, 0); for(int i = 0; i < n; ++i) { st[i] = Seg[i].first; dr[i] = Seg[i].second; if(i) { sb[i] = (dr[i] - st[i]) * (dr[i] - st[i]); if(dr[i - 1] > st[i]) sb[i] -= (dr[i - 1] - st[i]) * (dr[i - 1] - st[i]); sb[i] += sb[i - 1]; } } auto cost = [&](int i, int j) { return (dr[j] - st[i]) * (dr[j] - st[i]) - (dr[i] - st[i]) * (dr[i] - st[i]) - sb[j] + sb[i]; return dr[j] * dr[j] - sb[j] + 2 * st[i] * dr[i] - dr[i] * dr[i] + sb[i] - 2 * st[i] * dr[j]; }; ll re0 = 0; for(int i = 0; i < n; ++i) re0 += (dr[i] - st[i]) * (dr[i] - st[i]); const ll INF = 1e16; vector<vector<ll> > DP(n, vector(k + 1, INF)); for(int i = 0; i < n; ++i) { DP[i][1] = cost(0, i); for(int j = 2; j <= k; ++j) { for(int p = 1; p <= i; ++p) DP[i][j] = min(DP[i][j], DP[p - 1][j - 1] + cost(p, i)); } } ll re = INF; for(auto it : DP[n - 1]) re = min(re, it); re += re0; return re; }
#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...