Submission #966971

#TimeUsernameProblemLanguageResultExecution timeMemory
966971MarwenElarbiAliens (IOI16_aliens)C++17
12 / 100
15 ms620 KiB
//#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)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:10:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     if(k>=st.size()) return st.size();
      |        ~^~~~~~~~~~~
aliens.cpp:15:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for (int i = 0; i < tab.size(); ++i)
      |                     ~~^~~~~~~~~~~~
aliens.cpp:24:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for (int i = 1; i < tab.size(); ++i)
      |                     ~~^~~~~~~~~~~~
#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...