제출 #313275

#제출 시각아이디문제언어결과실행 시간메모리
313275anakib1Aliens (IOI16_aliens)C++17
41 / 100
899 ms119672 KiB
//나는 가상 소녀들에게 큰 호감이 있습니다. #include <iostream> #include <cmath> #include <algorithm> #include <stdio.h> #include <cstring> #include <string> #include <cstdlib> #include <vector> #include <bitset> #include <map> #include <chrono> #include <functional> #include <unordered_set> #include <unordered_map> #include <numeric> #include <queue> #include <ctime> #include <stack> #include <set> #include <list> #include <deque> #include <iomanip> #include <sstream> #include <fstream> #include <stdarg.h> #include <utility> using namespace std; #define pb push_back #define mp make_pair #define ll long long #define ull unisgned long long #define ld long double #define all(a) a.begin(), a.end() #define SORT(a) sort(all(a)) #define pii pair<int, int> #define tii triple<int, int, int> #define e 1e-7 #define PI acos(-1) #define sz(a) (int)(a.size()) #define inf 1e17 #define vi vector<int> #define F first #define S second #define rng(x) for(int _ = 0; _ < (x); _++) #define rngi(i, x) for(int i = 0; i < (x); i++) #define rngsi(s, i, x) for(int i = (s); i <(x); i++) #define problem "a" template<typename A, typename B, typename C> struct triple { A X; B Y; C Z; triple(A a = 0, B b = 0, C c = 0) :X(a), Y(b), Z(c) {} }; template<typename A, typename B, typename C> triple<A, B, C> make_triple(A a = 0, B b = 0, C c = 0) { return triple<A, B, C>(a, b, c); } template<typename A, typename B, typename C> bool operator<(const triple<A, B, C>& a, const triple<A, B, C>& b) { if (a.X != b.X) return a.X < b.X; if (a.Y != b.Y) return a.Y < b.Y; return a.Z < b.Z; } template<typename T, typename SS> ostream& operator<<(ostream& ofs, const pair<T, SS>& p) { ofs << "( " << p.F << " , " << p.S << " )"; return ofs; } template<typename T> void print(T a) { for (auto i : a) cout << i << ' '; cout << '\n'; } template<typename T> T max(T a, T b, T c) { return max(a, max(b, c)); } template<typename T> T min(T a, T b, T c) { return min(a, min(b, c)); } template<typename T, typename D> D min(T a) { return *min_element(all(a)); } template<typename T, typename D> D max(T a) { return *max_element(all(a)); } struct custom_hash { static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; ll f[4002][4002]; int d[4002][4002]; long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { vector<pair<ll, ll> > a; rngi(i, n) a.push_back({ min(r[i], c[i]), max(r[i], c[i]) }); sort(all(a), [&](auto &x, auto &y) {return x.first < y.first || (x.first == y.first && x.second > y.second); }); vector<pair<ll, ll> > b; rngi(i, n) if (!sz(b) || b.back().second < a[i].second) b.push_back(a[i]); n = sz(b); rngi(i, n + 1) rngi(j, k + 1) f[i][j] = inf; rngi(i, k + 1) f[0][i] = 0; auto sq = [&](int x)->ll {return x * 1LL * x; }; for(int j = 1; j <= k; j++) for (int i = n; i >= 1; i--) { int l = (j ? d[i][j - 1] : 0), u = (i < n ? d[i + 1][j] : i - 1); auto fx = [&](int t) -> ll{ return f[t][j - 1] + sq(b[i - 1].second - b[t].first + 1) - sq(max(0LL, (t ? (b[t - 1].second - b[t].first + 1) : 0LL))); }; int pos = l; for (int t = l; t <= u; t++) if (fx(pos) >= fx(t)) pos = t; d[i][j] = pos; f[i][j] = fx(pos); } //for (int i = 1; i <= n; i++) for (int j = 1; j <= k; j++) rngi(t, i) f[i][j] = min(f[i][j], ); return f[n][k]; } /* 5 7 2 0 3 4 4 4 6 4 5 4 6 */
#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...