제출 #69257

#제출 시각아이디문제언어결과실행 시간메모리
69257SmsSAliens (IOI16_aliens)C++14
4 / 100
93 ms4716 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define for2(a,b,c) for(int a=b;a < c; a++) #include "aliens.h" int dp[510][1010]; int tmp[510][1010]; int R[1010]; int C[1010]; long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { if (n > 500) return -1; fill(R,R+m+2,(1e9)); fill(C,C+m+2,(1e9)); for2(i,0,n){ R[r[i]]= min(R[r[i]],c[i]); C[c[i]]= min(C[c[i]],r[i]); } for2(i,0,510) for2(j,0,1010){ if(i <= k) dp[i][j] = 0; else dp[i][j] = 1e9; } for2(i,1,m+1){ for2(i,0,510) for2(j,0,1010){ tmp[i][j] = dp[i][j]; dp[i][j] = (1e9); } for2(j,0,k+1) for2(t,0,i+1){ int nt = t; nt = min(nt,C[i-1]); nt = min(nt,R[i-1]); if(j) dp[j][t] = min((ll)dp[j][t],tmp[j-1][nt] + (i-nt)*1ll*(i-nt) - (i-t)*1ll*(i-t) ); if(nt == t) dp[j][t] = min(dp[j][t],tmp[j][t]); if(nt == t && nt == i){ dp[j][t] = min(dp[j][t],tmp[j][t-1]); } } } return dp[k][m]; }
#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...