제출 #962451

#제출 시각아이디문제언어결과실행 시간메모리
962451RaresFelixAliens (IOI16_aliens)C++17
100 / 100
946 ms17100 KiB
#include <bits/stdc++.h> #include "aliens.h" //#pragma GCC optimize("O3") //#pragma GCC target("avx,avx2,fma") #define sz(x) int((x).size()) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() using namespace std; using ll = long long; using ld = long double; // or double, if TL is tight using str = string; using ii = pair<int, int>; using pl = pair<ll, ll>; using vi = vector<int>; using vll = vector<ll>; const ll INF = 1e16; struct CHT { int p = 0; vector<pair<ld, ld>> V; void insert(ld a, ld b) { /// add ax + b while(V.size() > 1) { auto [a1, b1] = V.end()[-2]; auto [a2, b2] = V.end()[-1]; if((b1 - b2) * (a - a2) >= (b2 - b) * (a2 - a1)) { V.pop_back(); } else break; } V.push_back({a, b}); } ld query(ld x) { if(V.empty()) return 1e30; auto eval = [&](pair<ld, ld> f) { return f.first * x + f.second; }; while(p + 1 < V.size() && eval(V[p]) >= eval(V[p + 1])) ++p; return eval(V[p]); } }; ll take_photos(int n0, int m, int k, vi r, vi c) { vector<ii> SegInit; for(int i = 0; i < n0; ++i) { SegInit.push_back({min(r[i], c[i]), max(r[i], c[i]) + 1}); } sort(all(SegInit), [&](auto a, auto b) { if(a.first != b.first) return a < b; return a > b; }); vector<ii> Seg; int cur_dr = -1; for(auto [st, dr] : SegInit) { if(dr <= cur_dr) continue; else { Seg.push_back({st, dr}); cur_dr = dr; } } int n = Seg.size(); vll st(n, 0), dr(n, 0), sb(n, 0); for(int i = 0; i < n; ++i) { st[i] = Seg[i].first; dr[i] = Seg[i].second; sb[i] = (dr[i] - st[i]) * (dr[i] - st[i]); if(i) { if(dr[i - 1] > st[i]) sb[i] -= (dr[i - 1] - st[i]) * (dr[i - 1] - st[i]); sb[i] += sb[i - 1]; } } auto cost = [&](int i, int j) { return (dr[j] - st[i]) * (dr[j] - st[i]) - (dr[i] - st[i]) * (dr[i] - st[i]) - sb[j] + sb[i]; return (dr[j] * dr[j] - sb[j]) + (2 * st[i] * dr[i] - dr[i] * dr[i] + sb[i]) - 2 * st[i] * dr[j]; }; ll re0 = sb.back(); auto t = [&](ld lambda) { ld re = - lambda * k; CHT Sol; vector<ld> DP(n, 0.); for(int i = 0; i < n; ++i) { ld dpant = 0.; if(i) dpant = DP[i - 1]; Sol.insert(- 2 * st[i], (dpant + (2 * st[i] * dr[i] - dr[i] * dr[i] + sb[i]))); DP[i] = lambda + (ld)cost(0, i); ld v = lambda + (Sol.query(dr[i]) + dr[i] * dr[i] - sb[i]); DP[i] = min(DP[i], v); } re += DP.back(); return re; }; ld re = 0; ld s = 0, d = 1e14, mij; ld vm = 0; for(int i = 0; i < 100; ++i) { ld m1 = (2 * s + d) / 3, v1 = t(m1); ld m2 = (s + 2 * d) / 3, v2 = t(m2); vm = max(vm, v1); vm = max(vm, v2); if(v1 < v2) s = m1; else d = m2; } re = ll(round(vm) + 1e-8); re += re0; return re; }

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

aliens.cpp: In member function 'ld CHT::query(ld)':
aliens.cpp:39:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         while(p + 1 < V.size() && eval(V[p]) >= eval(V[p + 1])) ++p;
      |               ~~~~~~^~~~~~~~~~
aliens.cpp: In function 'll take_photos(int, int, int, vi, vi)':
aliens.cpp:101:25: warning: unused variable 'mij' [-Wunused-variable]
  101 |     ld s = 0, d = 1e14, mij;
      |                         ^~~
#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...