제출 #58387

#제출 시각아이디문제언어결과실행 시간메모리
58387FLDutchmanAliens (IOI16_aliens)C++14
60 / 100
2074 ms385036 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; typedef int INT; #define pb push_back #define FOR(i, l, r) for(int i = (l); i < (r); i++) #define fst first #define snd second #define int long long typedef vector<int> vi; typedef pair<int, int> ii; typedef vector<ii> vii; typedef long long ll; const ll INF = 1e15; struct line{ int m, q; line (int M, int Q) { m = M; q = Q; } bool operator< (const line &l){ return make_pair(m, q) < make_pair(l.m, l.q); } int eval(int x){ return m*x+q; } }; double intersect(const line &l1, const line &l2){ return (long double) (l1.q - l2.q) / (l2.m - l1.m); } bool bad(const line &l1, const line &l2, const line &l3){ return (l3.q-l2.q) * (l2.m - l1.m) < (l1.q - l2.q) * (l2.m - l3.m); } // MAX hull, slopes increasing struct hull{ deque<line> slopes; void insert(line l){ while(slopes.size() >= 2 and bad(*prev(slopes.end(), 2), slopes.back(), l)) slopes.pop_back(); slopes.push_back(l); } int get(int x){ while(slopes.size() != 1 and slopes[0].eval(x) <= slopes[1].eval(x)) slopes.pop_front(); return slopes[0].eval(x); } }; vi C, R; vii points; int sqr(int x) {return x*x;} long long take_photos(INT n, INT m, INT k, std::vector<INT> r, std::vector<INT> c) { FOR(i, 0, n) if(c[i] < r[i]) swap(r[i], c[i]); FOR(i, 0, n) points.pb({r[i], c[i]}); points.pb({INF, INF}); sort(points.begin(), points.end()); FOR(i, 0, n){ if(points[i].fst != points[i+1].fst){ if(C.size() == 0 || points[i].snd > C.back()) {R.pb(points[i].fst); C.pb(points[i].snd);} } } //FOR(i, 0, C.size()){ // cout << R[i] << " " << C[i] << endl; //} vector<vi> dp; int N = C.size(); dp.assign(N+1, vi(k+1, -1)); FOR(i, 0, N) dp[i][0] = INF; FOR(K, 0, k+1) dp[N][K] = 0; FOR(K, 1, k+1){ hull h; for(int i = N-1; i >= 0; i--){ h.insert({2*(C[i] +1), -sqr(C[i]+1) - dp[i+1][K-1]}); dp[i][K] = sqr(R[i]) - ( i == 0 ? 0 : sqr(max(0LL, C[i-1] + 1 - R[i])) ) - h.get(R[i]); //int mi = INF; //FOR(j, i+1, N+1) mi = min(mi, dp[j][K-1] + sqr(C[j-1]+1 - R[i]) - (i == 0 || C[i-1]+1-R[i] < 0 ? 0 : sqr(C[i-1]+1-R[i]) ) ); //dp[i][K] = mi; } } //FOR(K, 0, k+1) { // FOR(i, 0, N+1) cout << dp[i][K] << " "; // cout<<endl; //} return dp[0][k]; } /* 5 7 2 0 3 4 4 4 6 4 5 4 6 4 7 2 4 4 4 6 4 5 4 6 2 7 2 0 1 1 3 2 7 2 0 1 5 7 */
#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...