제출 #1084896

#제출 시각아이디문제언어결과실행 시간메모리
1084896fyanAliens (IOI16_aliens)C++14
100 / 100
167 ms8148 KiB
#include "bits/stdc++.h" using namespace std; #define int int64_t #define all(x) begin(x), end(x) #define sz(x) (int) (x).size() const int MXN=1e5+5, INF=1e9; int N,M,K; array<int,2> arr[MXN]; int dp[MXN], amt[MXN]; bool cc1(const array<int,2> &a, const array<int,2> &b) { if (a[0]==b[0]) { return a[1]>b[1]; } return a[0]<b[0]; } bool cc2(const array<int,2> &a, const array<int,2> &b) { return a[1]<b[1]; } namespace monoline { const int lo = -10, hi = 1e6+5; deque<array<int,5>> lines; void reset() {while (sz(lines)) lines.pop_back();} int eval(array<int,5> a, int x) { return a[0]*x+a[1]; } int first_lower(array<int,5> a, array<int,5> b) { if (eval(a,lo)<=eval(b,lo) && eval(a,hi)<=eval(b,hi)) {return -69420;} if (eval(a,lo)>=eval(b,lo) && eval(a,hi)>=eval(b,hi)) {return 0;} int fp = (a[1]-b[1])/(b[0]-a[0]); fp--; while (eval(a,fp) <= eval(b,fp)) { fp++; } return fp; } void insert_line(int m, int b, int v=0) { array<int,5> ln = {m,b,v,-69,-69}; while (1) { if (!sz(lines)) { ln[3] = lo, ln[4] = hi; lines.push_back(ln); return; } array<int,5>& pv = lines.back(); pv[4] = hi; int fp = first_lower(pv,ln); if (fp==-69420) return; if (fp <= pv[3]) { lines.pop_back(); continue; } pv[4] = fp-1; ln[3] = fp, ln[4] = hi; lines.push_back(ln); return; } } array<int,2> get_value(int x) { while (lines.front()[4] < x) { lines.pop_front(); } int vv = eval(lines.front(),x); if (sz(lines)>1) { auto temp = lines.front(); lines.pop_front(); if (eval(lines.front(),x) >= vv) { lines.push_front(temp); } } return {eval(lines.front(),x),lines.front()[2]}; } } int check(int w) { memset(dp,0x3f,sizeof(dp)); memset(amt,0,sizeof(amt)); dp[0] = 0; monoline::reset(); monoline::insert_line(-2*(arr[0+1][0]-1), dp[0] + (arr[0+1][0]-1)*(arr[0+1][0]-1) - (max(0ll,arr[0][1]-arr[0+1][0]+1ll))*(max(0ll,arr[0][1]-arr[0+1][0]+1ll)),0); for (int i=1; i<=N; i++) { auto [v,a] = monoline::get_value(arr[i][1]); dp[i] = v+w+arr[i][1]*arr[i][1]; amt[i] = a+1; monoline::insert_line(-2*(arr[i+1][0]-1), dp[i] + (arr[i+1][0]-1)*(arr[i+1][0]-1) - (max(0ll,arr[i][1]-arr[i+1][0]+1ll))*(max(0ll,arr[i][1]-arr[i+1][0]+1ll)),amt[i]); } return amt[N]; } int search(int lo, int hi) { if (lo==hi) return lo; if (lo+1==hi) { if (check(hi)==K) return hi; return lo; } int mid = (lo+hi)/2; if (check(mid) <= K) { return search(lo,mid); } return search(mid,hi); } int take_photos(int32_t n, int32_t m, int32_t k, vector<int32_t> r, vector<int32_t> c) { N = n, M = m, K = k; for (int i=1; i<=N; i++) { arr[i] = {min(r[i-1],c[i-1]),max(r[i-1],c[i-1])}; } arr[0] = {-INF,-INF}; sort(arr,arr+N+1,cc1); int pv = 0,sub = 0; for (int i=1; i<=N; i++) { if (arr[pv][1] >= arr[i][1]) { sub++; arr[i] = {INF,INF}; } else pv = i; } sort(arr,arr+1+N,cc2); N -= sub; K = min(K,N); int w = search(-1e12,1e12); check(w); while (amt[N] > K) { w++; check(w); } return dp[N]-w*(K); } /* signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int32_t a,b,c; cin>>a>>b>>c; vector<int32_t> x(a),y(a); for (int i=0; i<a; i++) { cin>>x[i]>>y[i]; } cout<<take_photos(a,b,c,x,y); return 0; } */

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

aliens.cpp: In function 'int64_t check(int64_t)':
aliens.cpp:84:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   84 |   auto [v,a] = monoline::get_value(arr[i][1]);
      |        ^
#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...