제출 #137900

#제출 시각아이디문제언어결과실행 시간메모리
137900nashAliens (IOI16_aliens)C++14
0 / 100
2041 ms632 KiB
#include <bits/stdc++.h> #include "aliens.h" using namespace std; long long int mnsquares = 1000000000; vector<int> r, c; int n; //tehere is no point having overlapping squares //at every point on the diagonal we have 2 choices - start a square here or not //if we do, try making the square any size between 1 and thew max long long int dp(int k, int m, int covered, int idx, vector<int> got, int nogot){ if (k<0) return 100000000000; if (k==0 || idx==m){ //if (got==0) return 100000000000; if (nogot!=n) return 10000000000; //cout << k << ' ' << idx << ' ' << covered << ' ' << n << ' ' << nogot << endl; return covered; //we made it pat the end } long long int ans = dp(k, m, covered, idx+1, got, nogot); //i is size of photo for (int i=0;i<=m-idx;i++){ if (i==0){ vector<int> newgot=got; int nnogot=nogot; for (int a=0;a<n;a++){ if (r[a]==idx && c[a]==idx){ if (newgot[a]==0) nnogot++; newgot[a]=1; } else if (r[a]<idx && c[a]<idx && newgot[a]==0) return 100000000000000; } ans=min(ans, dp(k-1, m, covered+1, idx+1, newgot, nnogot)); continue; } vector<int> newgot=got; int nnogot=nogot; for (int a=0;a<n;a++){ if (r[a]>=idx && r[a]<=idx+i && c[a]>=idx && c[a]<=idx+i){ if (newgot[a]==0) nnogot++; newgot[a]=1; } else if (r[a]<idx && c[a]<idx && newgot[a]==0) return 100000000000000; } ans=min(ans, dp(k-1, m, covered+((i+1)*(i+1)), idx+1, newgot, nnogot)); } return ans; } long long int take_photos(int N, int m, int k, vector<int> R, vector<int> C){ n=N; r=R; c=C; return dp(k, m, 0, 0, vector<int> (N, 0), 0); }
#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...