제출 #427298

#제출 시각아이디문제언어결과실행 시간메모리
427298vincentpikachu20Aliens (IOI16_aliens)C++17
16 / 100
144 ms2320 KiB
#include <bits/stdc++.h> #include "aliens.h" #define int long long using namespace std; vector<vector<int>> mem; int dp(vector<int> &a, int n, int i, int k){ if(mem[i][k] != -1) return mem[i][k]; if(i == n) return mem[i][k] = 0; if(k == 0) return mem[i][k] = 1e18; int ans = 1e18; for(int j = i; j < n; j ++){ ans = min(ans, (a[j]-a[i]+1)*(a[j]-a[i]+1) + dp(a,n,j+1,k-1)); } return mem[i][k] = ans; } int take_photos(signed n, signed m, signed k, vector<signed> r, vector<signed> c) { if(n <= 50 && m <= 100 && k == n){ int ans = 0; vector<vector<bool>> a(m,vector<bool>(m)); for(int i = 0; i < n; i ++){ int mi = min(r[i],c[i]); int ma = max(r[i],c[i]); for(int j = mi; j <= ma; j ++){ for(int k = mi; k <= ma; k ++){ if(!a[j][k]) ans ++; a[j][k] = true; } } } return ans; }else{ r.erase(unique(r.begin(), r.end()), r.end()); sort(r.begin(), r.end()); vector<int> rr(r.begin(), r.end()); n = rr.size(); mem = vector<vector<int>>(n+1,vector<int>(k+1,-1)); return dp(rr,n,0,k); } }
#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...