# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
966971 | MarwenElarbi | Aliens (IOI16_aliens) | C++17 | 15 ms | 620 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c){
set<int> st;
for (int i = 0; i < n; ++i)
{
st.insert(r[i]);
}
if(k>=st.size()) return st.size();
vector<int> tab;
tab.push_back(-1);
for(auto u:st) tab.push_back(u);
int dp[tab.size()+1][k+1];
for (int i = 0; i < tab.size(); ++i)
{
for (int j = 0; j <= k; ++j)
{
dp[i][j]=1e9;
}
}
int ans=m*m;
dp[0][0]=0;
for (int i = 1; i < tab.size(); ++i)
{
int lst=tab[i];
int cur=1;
//cout <<i<<endl;
for (int j = i; j >= 0 ; --j)
{
//cout <<i<<" "<<j<<" "<<cur<<" "<<dp[j-1][1]<<endl;
if(j==0){
//cout <<i<<endl;
//cout <<"nabba"<<endl;
dp[i][1]=cur*cur;
}else{
//cout <<"nabba"<<endl;
cur+=lst-tab[j];
lst=tab[j];
for (int t = 1; t <= k; ++t)
{
//cout <<i<<" "<<t<<endl;
dp[i][t]=min(dp[i][t],dp[j-1][t-1]+cur*cur);
//cout <<dp[i][t]<<endl;
}
}
}
}
for (int i = 0; i <= k; ++i)
{
ans=min(ans,dp[tab.size()-1][k]);
}
return ans;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |