제출 #1118815

#제출 시각아이디문제언어결과실행 시간메모리
1118815vjudge1Aliens (IOI16_aliens)C++17
0 / 100
2 ms612 KiB
// #pragma comment(linker, "/stack:200000000") // #pragma GCC optimize("Ofast") // #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4") // #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt") #include "aliens.h" // #define _GLIBCXX_DEBUG // #define _GLIBCXX_DEBUG_PEDANTIC #include <iomanip> #include <cassert> #include <iostream> #include <vector> #include <random> #include <algorithm> #include <map> #include <set> #include <functional> #include <array> #include <numeric> #include <queue> #include <deque> #include <bitset> #include <cmath> #include <climits> #include <cstdint> // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> // #include <ext/rope> // using namespace __gnu_pbds; // using namespace __gnu_cxx; using namespace std; const int MOD = 998244353; const long double PI = 3.141592653589793; using ll = long long; const ll INF = 1e18; // #define int ll // --------> sashko123`s defines: #define itn int //Vasya sorry :( #define p_b push_back #define fi first #define se second #define pii std::pair<int, int> #define oo LLONG_MAX #define big INT_MAX #define elif else if int input() { int x; cin >> x; return x; } // ----------> end of sashko123`s defines (thank you Vasya <3) // template<typename K, typename V> // using hash_table = cc_hash_table<K, V, hash<K>>; // template<typename T> // using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; // int n, m, k; vector<pii> a; const int N = 600; const int K = 600; ll dp[N][K]; ll W(ll l, ll r) { return (r - l + 1) * (r - l + 1); } vector<pii> recalc(vector<pii> a, int n) { sort(a.begin(), a.end(), [&](pii x, pii y) { return tuple{x.second, x.first} < tuple{y.second, y.first}; }); set<pii> st; for (int i = 0; i < n; i++) { auto [l, r] = a[i]; while (!st.empty() && st.rbegin()->first >= l) { st.erase(prev(st.end())); } st.insert({l, r}); } return vector(st.begin(), st.end()); } ll take_photos(int n, int m, int k, vector<int> rr, vector<int> cc) { // cin >> n >> m >> k; a.resize(n); for (int i = 0; i < n; i++) { int r = rr[i], c = cc[i]; // cin >> r >> c; if (r > c) swap(r, c); a[i] = {r, c}; } a = recalc(a, n); n = a.size(); a.insert(a.begin(), {0, 0}); // cerr << a.size() << "\n"; dp[0][0] = 0; for (int i = 1; i <= n; i++) { for (int c = 1; c <= k; c++) { // cerr << a[1].first << " " << a[i].second << " " << W(a[1].first, a[i].second) << endl; dp[i][c] = dp[0][c - 1] + W(a[1].first, a[i].second); for (int t = 1; t < i; t++) { ll cur = dp[t][c - 1] + W(a[t + 1].first, a[i].second) - W(a[t + 1].first, a[t].second); dp[i][c] = min(dp[i][c], cur); } } } return dp[n][k]; } // int32_t main(int32_t argc, const char * argv[]) { // cin.tie(0); // cout.tie(0); // ios_base::sync_with_stdio(0); // // insert code here... // int tt= 1; // // std::cin >> tt; // for (int t = 1; t <= tt; t++) { // // cout << "Case #" << t << ": "; // solve(); // } // return 0; // }
#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...