제출 #400281

#제출 시각아이디문제언어결과실행 시간메모리
400281rocks03Aliens (IOI16_aliens)C++14
12 / 100
243 ms324 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int, int> #define pll pair<ll, ll> #define ff first #define ss second #define pb push_back #define SZ(x) ((int)(x).size()) #define all(x) x.begin(), x.end() #define debug(x) cout << #x << ": " << x << " " #define nl cout << "\n" #define rep(i, a, b) for(int i = (a); i < (b); i++) #define per(i, a, b) for(int i = (a); i >= (b); i--) mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); long long take_photos(int N, int M, int K, vector<int> X, vector<int> Y){ vector<pll> v(N); rep(i, 0, N) v[i] = {X[i], Y[i]}; sort(all(v)); vector<ll> dp(N + 1, LLONG_MAX), dp2; dp[0] = 0; dp2 = dp; rep(k, 1, K + 1){ rep(i, 0, N){ ll mn, mx; mn = min(v[i].ff, v[i].ss); mx = max(v[i].ff, v[i].ss); per(j, i, 0){ mn = min({mn, v[j].ff, v[j].ss}); mx = max({mx, v[j].ff, v[j].ss}); ll cost = (mx - mn + 1) * (mx - mn + 1); if(dp[j] != LLONG_MAX){ dp2[i + 1] = min(dp2[i + 1], dp[j] + cost); } } } swap(dp, dp2); } return dp[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...