제출 #773638

#제출 시각아이디문제언어결과실행 시간메모리
773638petezaAliens (IOI16_aliens)C++14
12 / 100
47 ms3220 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; long long dp[4005][4005]; long long square(long long x) { x = max(0ll, x); return x*x; } long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { std::vector<pii> points; std::vector<pii> rps; for(int i=0;i<n;i++) { if(r[i] < c[i]) points.emplace_back(r[i], c[i]); else points.emplace_back(c[i], r[i]); } sort(points.begin(), points.end(), [](pii a, pii b){return a.first < b.first || (a.first == b.first && a.second > b.second);}); int last = -1; for(auto e:points) { if(last == e.first) continue; while(!rps.empty() && rps.back().second >= e.second) rps.pop_back(); if(rps.empty() || rps.back().second < e.second) rps.emplace_back(e); last = e.first; } k = min(k, (int) rps.size()); for(int i=0;i<rps.size();i++) dp[i][0] = square(rps[i].second-rps[0].first+1)/*, cout << dp[i][0] << ' '*/; for(int j=1;j<k;j++) { for(int i=j;i<rps.size();i++) { dp[i][j] = 1000000000000000000ll; for(int k=j-1;k<i;k++) { dp[i][j] = min(dp[i][j], dp[k][j-1] - square(rps[k].second-rps[k+1].first+1) + square(rps[i].second-rps[k+1].first+1)); } } } return dp[rps.size()-1][k-1]; } /* #include <cstdio> #include <cassert> 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; } */

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

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i=0;i<rps.size();i++) dp[i][0] = square(rps[i].second-rps[0].first+1)/*, cout << dp[i][0] << ' '*/;
      |                 ~^~~~~~~~~~~
aliens.cpp:30:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for(int i=j;i<rps.size();i++) {
      |                     ~^~~~~~~~~~~
#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...