제출 #522420

#제출 시각아이디문제언어결과실행 시간메모리
522420lohachoAliens (IOI16_aliens)C++14
25 / 100
6 ms5128 KiB
#include "aliens.h" #include <bits/stdc++.h> #define mi(x, y) (x = min(x, y)) #define ma(x, y) (x = max(x, y)) using namespace std; const long long NS = (long long)2e5 + 4; long long n; vector<long long> line[NS]; long long f, r; long long cross(vector<long long> x, vector<long long> y){ long long val = (x[1] - y[1]) / (y[0] - x[0]); return val + (val >= 0 && (x[1] - y[1]) % (y[0] - x[0]) ? 1 : 0); } void push(long long a, long long b, long long c){ while(f + 1 < r && cross({a, b}, line[r - 1]) <= cross(line[r - 1], line[r - 2])) --r; line[r++] = {a, b, c}; } pair<long long, long long> get(long long x){ while(f + 1 < r && line[f][0] * x + line[f][1] >= line[f + 1][0] * x + line[f + 1][1]) ++f; return {line[f][0] * x + line[f][1], line[f][2]}; } long long take_photos(int n, int m, int k, std::vector<int> R, std::vector<int> C) { vector<pair<long long, long long>> a(n); for(long long i = 0; i < n; ++i){ a[i].first = R[i], a[i].second = C[i]; if(a[i].first > a[i].second){ swap(a[i].first, a[i].second); } } sort(a.begin(), a.end()); vector<pair<long long, long long>> stk = {a[0]}; for(long long i = 1; i < n; ++i){ if(stk.back().first == a[i].first) ma(stk.back().second, a[i].second); else if(stk.back().second < a[i].second) stk.push_back(a[i]); } a = stk; n = (long long)a.size(); long long low = (long long)-1e13, high = (long long)1e13; auto sol = [&](long long pl)->pair<long long, long long>{ f = r = 0; vector<pair<long long, long long>> dp(n); push(-(a[0].first - 1) * 2 * 2, (a[0].first - 1) * (a[0].first - 1) * 2, 0); for(long long i = 0; i < n; ++i){ auto rv = get(a[i].second); dp[i] = {rv.first + a[i].second * a[i].second * 2 + pl, rv.second + 1}; auto nsame = 0; if(i + 1 < n && a[i + 1].first <= a[i].second){ nsame = (a[i].second - a[i + 1].first + 1) * (a[i].second - a[i + 1].first + 1); } if(i + 1 < n) push(-(a[i + 1].first - 1) * 2 * 2, ((a[i + 1].first - 1) * (a[i + 1].first - 1) - nsame) * 2 + dp[i].first, dp[i].second); } return dp[n - 1]; }; mi(k, n); while(low < high){ long long mid = low + high >> 1; auto rv = sol(mid * 2 + 1); //cout << low << ' ' << high << ' ' << mid << ' ' << rv.first << ' ' << rv.second << endl; if(rv.second <= k){ high = mid; } else{ low = mid + 1; } } low = low * 2; auto rv = sol(low); //cout << rv.first << ' ' << rv.second << ' ' << low << endl; return ((rv.first - k * low) >> 1); }

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

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:60:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |         long long mid = low + high >> 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...