제출 #361889

#제출 시각아이디문제언어결과실행 시간메모리
3618892fat2codeAliens (IOI16_aliens)C++17
0 / 100
1 ms492 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define ld long double #define all(a) (a).begin(), (a).end() #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #define fr first #define sc second #define rc(s) return cout<<s,0 #define rcc(s) cout<<s,exit(0) int pt = 0; vector <pair<int, int>> segments; void erase_useless(){ vector <pair<int,int>> tz; for(auto it : segments){ if(!tz.size()){ tz.push_back(it); } else{ auto it1 = tz.back(); if(it1.fr >= it.fr && it1.sc <= it.sc){ tz.pop_back(); tz.push_back(it); } else if(it.fr >= it1.fr && it.sc <= it1.sc){ continue; } else{ tz.push_back(it); } } } segments = tz; } struct line{ int slope, cons; long double pbegin; }; long double intersect(line A, line B){ return (long double) (B.cons - A.cons) / (A.slope - B.slope); } struct CHT{ vector <line> hull; void add(line TZ){ if(hull.empty()){ TZ.pbegin = -1.0; hull.push_back(TZ); } else{ while((int)hull.size() >= 2){ if(intersect(TZ, hull.back()) <= intersect(hull.back(), hull[(int)hull.size() - 2])){ hull.pop_back(); } else{ break; } } TZ.pbegin = intersect(TZ, hull.back()); hull.push_back(TZ); } } int query(double x){ if(pt == (int)hull.size() - 1){ return hull[pt].slope * x + hull[pt].cons; } else{ while(hull[pt + 1].pbegin <= x){ ++pt; } return hull[pt].slope * x + hull[pt].cons; } } }; CHT solution; long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c){ vector < vector <int>> dp(n + 5, vector <int> (k + 5)); for(int i=0;i<n;i++){ segments.push_back({min(r[i], c[i]), max(r[i], c[i])}); } sort(all(segments)); erase_useless(); n = (int)segments.size(); segments.push_back({0, 0}); for(int i=1;i<=n;i++){ dp[i][1] = (segments[i - 1].sc - segments[0].fr + 1) * (segments[i - 1].sc - segments[0].fr + 1); } for(int j=2;j<=k;j++){ pt = 0; solution.hull.clear(); dp[1][j] = dp[1][j - 1]; solution.add({2 - 2*segments[1].fr, dp[1][j - 1] + (segments[1].fr - 1) * (segments[1].fr - 1) - max(0, segments[0].sc - segments[1].fr + 1) * max(0, segments[0].sc - segments[1].fr + 1), 0.0}); for(int i=2;i<=n;i++){ dp[i][j] = dp[i][j - 1]; dp[i][j] = min(dp[i][j], solution.query(segments[i - 1].sc) + segments[i - 1].sc * segments[i - 1].sc); solution.add({2 - 2*segments[i].fr, dp[i][j-1] + (segments[i].fr - 1) * (segments[i].fr - 1) - max(0, segments[i - 1].sc - segments[i].fr + 1) * max(0, segments[i - 1].sc - segments[i].fr + 1), 0.0}); } } return dp[n][k]; }
#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...