제출 #173922

#제출 시각아이디문제언어결과실행 시간메모리
173922gs18103Aliens (IOI16_aliens)C++14
0 / 100
2 ms376 KiB
#include "aliens.h" #include <bits/stdc++.h> #define fi first #define se second #define eb emplace_back #define em emplace #define all(v) v.begin(), v.end() using namespace std; typedef long long ll; typedef pair <int, int> pii; typedef pair <ll, ll> pll; const int MAX = 101010; const int INF = 1e9; const ll LINF = 1e18; const int mod = 1e9+7; ll dp[110][MAX]; vector <pll> line; double cross(pll a, pll b) {return (double)(b.se - a.se) / (a.fi - b.fi);} void add_line(pll l) { while(line.size() >= 2) { pll l1 = line[line.size()-2], l2 = line[line.size()-1]; if(cross(l1, l2) < cross(l2, l)) break; line.pop_back(); } line.eb(l); } //solution for nk log n long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) { vector <pii> tarr, arr; for(int i = 0; i < n; i++) { if(r[i] < c[i]) swap(r[i], c[i]); r[i]++; tarr.eb(r[i], c[i]); } sort(all(tarr)); arr.eb(0, -1); for(int i = 0; i < n; i++) { while(!arr.empty() && arr.back().se >= tarr[i].se) arr.pop_back(); arr.eb(tarr[i]); } n = arr.size() - 1; k = min(n, k); dp[0][0] = 0; for(int i = 1; i <= n; i++) dp[1][i] = (arr[i].fi - arr[1].se) * (arr[i].fi - arr[1].se); for(int i = 2; i <= k; i++) { int idx = 0; line.clear(); add_line(make_pair(-2*arr[1].se, arr[1].se * arr[1].se)); for(int j = 1; j <= n; j++) { while(idx + 1 < line.size() && cross(line[idx], line[idx+1]) <= (double)arr[j].fi) idx++; dp[i][j] = arr[j].fi * arr[j].fi + line[idx].fi * arr[i].fi + line[idx].se; if(j < n) add_line(make_pair(-2*arr[j+1].se, arr[j+1].se * arr[j+1].se + dp[i-1][j] - max(0, arr[j].fi-arr[j+1].se) * max(0, arr[j].fi - arr[j+1].se))); } } return dp[k][n]; }

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

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:55:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(idx + 1 < line.size() && cross(line[idx], line[idx+1]) <= (double)arr[j].fi) idx++;
                   ~~~~~~~~^~~~~~~~~~~~~
#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...