제출 #1018092

#제출 시각아이디문제언어결과실행 시간메모리
1018092khanhphucscratchAliens (IOI16_aliens)C++14
100 / 100
253 ms35704 KiB
#include<bits/stdc++.h> #include "aliens.h" #define int long long using namespace std; struct CHT { vector<pair<int, int>> line; vector<int> info; vector<double> hull; double intersection(pair<int, int> x, pair<int, int> y) { return (double)(x.second - y.second) / (y.first - x.first); } void addline(pair<int, int> x, int inf) { while(hull.size() > 0 && intersection(x, line[line.size()-1]) <= hull[hull.size()-1]){ hull.pop_back(); line.pop_back(); info.pop_back(); } if(line.size() > 0) hull.push_back(intersection(line[line.size()-1], x)); line.push_back(x); info.push_back(inf); } pair<int, int> bestval(int x) { if(line.size() == 0) return make_pair(1e15, 0); if(line.size() == 1) return make_pair(line[0].first*x+line[0].second, info[0]); int place = upper_bound(hull.begin(), hull.end(), x) - hull.begin(); //cout<<line.size()<<" "<<info.size()<<" "<<place<<" "<<info[1]<<endl; if(place > 0 && line[place].first*x+line[place].second == line[place-1].first*x+line[place-1].second) return make_pair(line[place].first*x+line[place].second, min(info[place], info[place-1])); else return make_pair(line[place].first*x+line[place].second, info[place]); } }; int dp[1000005], cnt[1000005], last[1000005]; inline bool cmp(pair<int, int> x, pair<int, int> y) { return x.second < y.second || (x.second == y.second && x.first > y.first); } int take_photos(int32_t n, int32_t m, int32_t k, vector<int32_t> r, vector<int32_t> c) { //Transform to segments vector<pair<int, int>> segment; for(int i = 0; i < n; i++){ if(r[i] <= c[i]) segment.push_back({r[i], c[i]+1}); else segment.push_back({c[i], r[i]+1}); } //Eliminate unnecessary segments sort(segment.begin(), segment.end(), cmp); vector<pair<int, int>> sus; for(pair<int, int> i : segment){ while(sus.size() > 0 && sus[sus.size()-1].first >= i.first){ sus.pop_back(); } sus.push_back(i); } memset(last, -1, sizeof(last)); for(pair<int, int> i : sus){ last[i.second] = i.first; //cout<<i.first<<" "<<i.second<<endl; } //O(m log n log eps^-1) dp int le = 0, ri = 1e12, ans = 1e18, lamdaval; while(le <= ri){ int lambd = (le+ri)/2; int lastplace = -1; CHT st; st.addline({0, 0}, 0); for(int i = 1; i <= m; i++){ if(last[i] > -1){ pair<int, int> newline; newline = make_pair(-2*last[i], last[i]*last[i]); if(last[i] < lastplace) newline.second -= (lastplace - last[i]) * (lastplace - last[i]); if(lastplace > -1) newline.second += dp[lastplace]; st.addline(newline, cnt[lastplace]); } if(last[i] == -1){ dp[i] = dp[i-1]; cnt[i] = cnt[i-1]; } else{ pair<int, int> sus = st.bestval(i); dp[i] = i*i + sus.first + lambd; cnt[i] = sus.second+1; lastplace = i; } //cout<<"A"<<i<<" "<<dp[i]<<" "<<cnt[i]<<endl; } if(cnt[m] <= k){ ri = lambd-1; ans = dp[m]; lamdaval = lambd; //cout<<lamdaval<<" "<<ans<<" "<<cnt[m]<<endl; } else{ le = lambd+1; } //cout<<lambd<<" "<<cnt[m]<<endl; //return 0; } return ans - k*lamdaval; } /*signed main() { cout<<take_photos(5, 6, 4, {0, 1, 2, 3, 4}, {1, 2, 3, 4, 5}); }*/

컴파일 시 표준 에러 (stderr) 메시지

aliens.cpp: In function 'long long int take_photos(int32_t, int32_t, int32_t, std::vector<int>, std::vector<int>)':
aliens.cpp:98:19: warning: 'lamdaval' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |     return ans - k*lamdaval;
      |                  ~^~~~~~~~~
#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...