제출 #136445

#제출 시각아이디문제언어결과실행 시간메모리
136445ckodserAliens (IOI16_aliens)C++14
60 / 100
415 ms27304 KiB
#include "aliens.h" #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <exception> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <locale> #include <map> #include <memory> #include <new> #include <numeric> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stack> #include <stdexcept> #include <streambuf> #include <string> #include <typeinfo> #include <utility> #include <valarray> #include <vector> #if __cplusplus >= 201103L #include <array> #include <atomic> #include <chrono> #include <condition_variable> #include <forward_list> #include <future> #include <initializer_list> #include <mutex> #include <random> #include <ratio> #include <regex> #include <scoped_allocator> #include <system_error> #include <thread> #include <tuple> #include <typeindex> #include <type_traits> #include <unordered_map> #include <unordered_set> #endif #define ll long long #define pb push_back #define mp make_pair #define ld long double #define F first #define S second #define pii pair<ll,ll> #define pdd pair<ld,ld> using namespace :: std; const ll maxn=50100; const ll inf=1e12+900; ld tav2(ld x){return x*x;} vector<pair<pdd,ll> > khat; vector<pair<ld,ll> > cht; ll poi; ld barkhord(ll a,ll b){ return (khat[a].F.F-khat[b].F.F)/(khat[b].F.S-khat[a].F.S); } void clearr(){ poi=0; khat.clear(); cht.clear(); } void add(ld x,ld v,ll h){ khat.pb(mp(mp(x,v),h)); ll i=khat.size()-1; while(cht.size() && barkhord(cht.back().S,i)<=cht.back().F)cht.pop_back(); if(cht.empty()){ cht.pb(mp(0,i)); }else{ cht.pb(mp(barkhord(cht.back().S,i),i)); } } pair<ld,ll> findMinAt(ld t){ if(cht.size()<=1)poi=0; else poi=min(poi,(ll)cht.size()-2); while(poi<cht.size()-1 && cht[poi+1].F<=t)poi++; ll v=cht[poi].S; return mp(khat[v].F.F+khat[v].F.S*t,khat[v].S); } vector<pii> vec; ll X[maxn]; ll V[maxn]; const ll maxm=1e6+100; ll mx[maxm]; ll cnt[maxn]; ld dp[maxn]; pair<ld,ll> solve(vector<pii> vec,ld mid){ clearr(); add(X[0],V[0],0); for(ll i=0;i<vec.size();i++){ pair<ld,ll> e=findMinAt(vec[i].F); dp[i]=e.F+tav2(vec[i].F)+mid; cnt[i]=e.S+1; add(X[i+1]+dp[i],V[i+1],cnt[i]); } return mp(dp[vec.size()-1],cnt[vec.size()-1]); } long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) { swap(n,m); fill(mx,mx+maxm,inf); for(ll i=0;i<m;i++){ if(c[i]>r[i]){ swap(c[i],r[i]); } mx[r[i]]=min(mx[r[i]],(ll)c[i]); } stack<ll> stk; for(ll i=0;i<n;i++){ while(stk.size() && mx[stk.top()]>=mx[i]){ stk.pop(); } if(mx[i]!=inf){ stk.push(i); } } while(stk.size()){ vec.pb(mp(stk.top(),mx[stk.top()])); stk.pop(); } sort(vec.begin(),vec.end()); X[0]=tav2(vec[0].S); V[0]=vec[0].S*-2; for(ll i=0;i+1<vec.size();i++){ X[i+1]=-tav2(max((ll)0,vec[i].F-vec[i+1].S+1))+tav2(vec[i+1].S); V[i+1]=vec[i+1].S*-2; } for(ll i=0;i<vec.size();i++){ vec[i].F++; } ld b=0; ld e=1e13; for(ll i=0;i<100;i++){ ld mid=(e+b)/2; pair<ld,ll> r=solve(vec,mid); if(r.S<=k){ e=mid; }else{ b=mid; } } pair<ld,ll> rr=solve(vec,e); return round(rr.F-k*e); }

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

aliens.cpp: In function 'std::pair<long double, long long int> findMinAt(long double)':
aliens.cpp:97:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(poi<cht.size()-1 && cht[poi+1].F<=t)poi++;
        ~~~^~~~~~~~~~~~~
aliens.cpp: In function 'std::pair<long double, long long int> solve(std::vector<std::pair<long long int, long long int> >, long double)':
aliens.cpp:116:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i=0;i<vec.size();i++){
             ~^~~~~~~~~~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:151:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i=0;i+1<vec.size();i++){
             ~~~^~~~~~~~~~~
aliens.cpp:155:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i=0;i<vec.size();i++){
             ~^~~~~~~~~~~
#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...