제출 #555621

#제출 시각아이디문제언어결과실행 시간메모리
555621BT21tataAliens (IOI16_aliens)C++17
16 / 100
79 ms1332 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; bool cover[505][505]; int cnt; long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) { if(k==n and n<=50) { for(int i=0; i<n; i++) { int x=r[i], y=c[i]; if(x>y) swap(x, y); for(int j=x; j<=y; j++) { for(int e=x; e<=y; e++) { cover[j][e]=1; } } } for(int i=0; i<m; i++) { for(int j=0; j<m; j++) { cnt+=cover[i][j]; } } return cnt; } else { set<int>s; vector<int>v; int dp[505][505]; for(int i=0; i<n; i++) { s.insert(r[i]); } for(auto it = s.begin(); it!=s.end(); ++it) { v.push_back(*it); } memset(dp, 63, sizeof(dp)); for(int i=0; i<(int)v.size(); i++) { dp[i][1]=(abs(v[0]-v[i])+1)*(abs(v[0]-v[i])+1); } for(int i=1; i<(int)v.size(); i++) { for(int j=2; j<=min(i+1, k); j++) { for(int u=0; u<i; u++) { dp[i][j]=min(dp[i][j], dp[u][j-1]+(abs(v[u+1]-v[i])+1)*(abs(v[u+1]-v[i])+1)); } } } int ans=1e9; //for(int i=0; i<(int)v.size(); i++) { for(int j=1; j<=k; j++) { ans=min(ans, dp[(int)v.size()-1][j]); } } return ans; } }
#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...