제출 #976629

#제출 시각아이디문제언어결과실행 시간메모리
976629leanchecAliens (IOI16_aliens)C++17
0 / 100
5 ms20948 KiB
#include "aliens.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; ll dp[110][50100]; vector<pair<int,int>> aux; ll sq(ll a){return a*a;} void solve(int qtd,int l, int r, int p, int q){ int mid=(l+r)>>1, opt=-1; for(int i=p; i<=min(q, mid-1); i++){ if(dp[qtd][mid]>dp[qtd-1][i]+sq(aux[mid].second-aux[i+1].first+1)-max((ll)0, sq(aux[i].second-aux[i+1].first+1))){ dp[qtd][mid]=dp[qtd-1][i]+sq(aux[mid].second-aux[i+1].first+1)-max((ll)0, sq(aux[i].second-aux[i+1].first+1)); opt=i; } } if(l<mid)solve(qtd, l, mid-1, p, opt); if(mid<r)solve(qtd, mid+1, r, opt, q); } long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { aux.clear(); for(int i=0; i<n; i++){ aux.push_back({min(r[i], c[i]), -max(r[i], c[i])}); } sort(aux.begin(), aux.end()); vector<pair<int,int>> temp; temp.push_back({-1, -1}); for(auto cur:aux){ if(-cur.second>temp.back().second)temp.push_back({cur.first, -cur.second}); } aux=temp; for(int i=1; i<=k; i++){ for(int j=1; j<=aux.size(); j++){ dp[i][j]=1e18; } } for(int i=1; i<aux.size(); i++) dp[1][i]=sq(aux[i].second-aux[i].first+1); for(int i=2; i<=min((int)aux.size()-1, k); i++) solve(i, 1, aux.size()-1, 1, aux.size()-1); return dp[min((int)aux.size()-1, k)][aux.size()-1]; }

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

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:39:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for(int j=1; j<=aux.size(); j++){
      |                ~^~~~~~~~~~~~
aliens.cpp:44:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for(int i=1; i<aux.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...