제출 #135958

#제출 시각아이디문제언어결과실행 시간메모리
135958ckodserAliens (IOI16_aliens)C++14
4 / 100
11 ms2808 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> using namespace :: std; const ll maxn=4100; const ll maxk=4010; const ll inf=1e9+900; ll tav2(ll x){return x*x;} ll sagh(ll a,ll b){ return (a+b-1)/b; } vector<pii> khat; vector<pii> cht; ll poi; ll barkhord(ll a,ll b){ return sagh((khat[a].F-khat[b].F),(khat[b].S-khat[a].S)); } void add(ll x[],ll v[],ll n){ poi=0; for(ll i=0;i<n;i++){ while(khat.size() && khat.back().F>=x[i])khat.pop_back(); khat.pb(mp(x[i],v[i])); } n=khat.size(); cht.clear(); cht.pb(mp(0,0)); for(ll i=1;i<n;i++){ while(cht.size() && barkhord(cht.back().F,i)<=cht.back().S)cht.pop_back(); if(cht.empty()){ cht.pb(mp(i,0)); }else{ cht.pb(mp(i,barkhord(cht.back().F,i))); } } /* for(ll i=0;i<n;i++){ cout<<x[i]<<' '<<v[i]<<" "; } cout<<endl; for(auto v:cht){ cout<<v.F<<' '<<v.S<<" : "; } cout<<endl;*/ } ll findMinAt(ll t){ while(poi<cht.size()-1 && cht[poi+1].S<=t)poi++; ll v=cht[poi].F; return khat[v].F+khat[v].S*t; } ll dp[maxn][maxk]; vector<pii> vec; ll XX[maxn]; ll X[maxn]; ll V[maxn]; ll mx[maxn]; long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) { swap(n,m); fill(mx,mx+maxn,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()); XX[0]=tav2(vec[0].S); V[0]=vec[0].S*-2; for(ll i=0;i+1<vec.size();i++){ XX[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++; } for(ll i=0;i<vec.size();i++){ dp[i][0]=inf; } for(ll j=1;j<=k;j++){ X[0]=XX[0]; for(ll i=1;i<vec.size();i++){ X[i]=XX[i]+dp[i-1][j-1]; } add(X,V,vec.size()); for(ll i=0;i<vec.size();i++){ dp[i][j]=min(inf,findMinAt(vec[i].F)+tav2(vec[i].F)); } } return dp[vec.size()-1][k]; }

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

aliens.cpp: In function 'long long int findMinAt(long long int)':
aliens.cpp:107:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(poi<cht.size()-1 && cht[poi+1].S<=t)poi++;
        ~~~^~~~~~~~~~~~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:148:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i=0;i+1<vec.size();i++){
             ~~~^~~~~~~~~~~
aliens.cpp:152:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i=0;i<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++){
             ~^~~~~~~~~~~
aliens.cpp:160:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ll i=1;i<vec.size();i++){
              ~^~~~~~~~~~~
aliens.cpp:164:15: 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...