제출 #23417

#제출 시각아이디문제언어결과실행 시간메모리
23417BruteforcemanAliens (IOI16_aliens)C++11
60 / 100
306 ms14224 KiB
#define JUDGE #ifndef JUDGE #include "aliens.h" #endif // JUDGE #include "bits/stdc++.h" using namespace std; typedef pair <int, int> pii; vector <pii> range; const long long INF = 1e16; bool comp(pii a, pii b) { if(a.first == b.first) { return a.second > b.second; } else { return a.first < b.first; } } long long count(int x, int y) { if(x <= y) return 1LL * (y - x + 1) * (y - x + 1); return 0; } long long dp[2][50005]; vector <long long> M; vector <long long> C; int pointer; bool bad(int x, int y, int z) { if(M[y] == M[z]) return true; return (C[y] - C[z]) * (M[z] - M[x]) <= (C[x] - C[z]) * (M[z] - M[y]); } void addLine(long long m, long long c) { if(!M.empty() && M.back() == m && C.back() < c) return ; M.push_back(m); C.push_back(c); while(M.size() >= 3 && bad(M.size() - 3, M.size() - 2, M.size() - 1)) { M.erase(M.end() - 2); C.erase(C.end() - 2); } } long long query(long long x) { if(M.empty()) return INF; if(pointer >= M.size()) { pointer = M.size() - 1; } while(pointer + 1 < M.size() && M[pointer] * x + C[pointer] >= M[pointer + 1] * x + C[pointer + 1]) { pointer++; } return M[pointer] * x + C[pointer]; } long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { set <pii> all; for(int i = 0; i < n; i++) { int x = min(r[i], c[i]); int y = max(r[i], c[i]); all.insert(make_pair(x, y)); } vector <pii> aux (all.begin(), all.end()); const int inf = 1e8; multiset <int> s; vector <pii> sweep; for(int i = 0; i < (int) aux.size(); i++) { sweep.push_back(make_pair(aux[i].first, inf)); sweep.push_back(make_pair(aux[i].second, aux[i].first)); } sort(sweep.begin(), sweep.end(), comp); for(int i = 0; i < (int) sweep.size(); i++) { if(sweep[i].second == inf) { s.insert(sweep[i].first); } else { if(*s.begin() == sweep[i].second) { if(s.size() == 1 || *(++s.begin()) != sweep[i].second) { range.push_back(pii(sweep[i].second, sweep[i].first)); } } s.erase(s.find(sweep[i].second)); } } range.push_back(make_pair(-1, -1)); sort(range.begin(), range.end()); int sz = range.size() - 1; memset(dp, 0, sizeof dp); for(int i = 1; i <= sz; i++) { dp[0][i] = INF; } int ro = 0; for(int i = 1; i <= k; i++) { ro ^= 1; M.clear(); C.clear(); pointer = 0; for(int j = 1; j <= sz; j++) { dp[ro][j] = INF; if(dp[ro ^ 1][j - 1] < INF) addLine(-2LL * range[j].first, 1LL * range[j].first * range[j].first + dp[ro ^ 1][j - 1] - count(range[j].first, range[j-1].second)); dp[ro][j] = min(dp[ro][j], query(range[j].second + 1) + 1LL * (range[j].second + 1) * (range[j].second + 1)); /* for(int l = 1; l <= j; l++) { dp[ro][j] = min(dp[ro][j], dp[ro ^ 1][l - 1] + count(range[l].first, range[j].second) - count(range[l].first, range[l-1].second)); dp[] } */ } } return dp[ro][sz]; } #ifndef JUDGE int main() { int n, m, k; assert(3 == scanf("%d %d %d", &n, &m, &k)); std::vector<int> r(n), c(n); for (int i = 0; i < n; i++) { assert(2 == scanf("%d %d", &r[i], &c[i])); } long long ans = take_photos(n, m, k, r, c); printf("%lld\n", ans); return 0; } #endif // JUDGE

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

aliens.cpp: In function 'long long int query(long long int)':
aliens.cpp:50:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(pointer >= M.size()) {
                ^
aliens.cpp:53:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pointer + 1 < M.size() && M[pointer] * x + C[pointer] >= M[pointer + 1] * x + C[pointer + 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...