# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
966971 | 2024-04-20T18:17:50 Z | MarwenElarbi | Aliens (IOI16_aliens) | C++17 | 15 ms | 620 KB |
//#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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 348 KB | Wrong answer: output = 1, expected = 4 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Correct answer: answer = 1 |
2 | Correct | 0 ms | 348 KB | Correct answer: answer = 4 |
3 | Correct | 0 ms | 344 KB | Correct answer: answer = 1 |
4 | Correct | 0 ms | 348 KB | Correct answer: answer = 5 |
5 | Correct | 0 ms | 348 KB | Correct answer: answer = 41 |
6 | Correct | 0 ms | 348 KB | Correct answer: answer = 71923 |
7 | Correct | 1 ms | 348 KB | Correct answer: answer = 77137 |
8 | Correct | 15 ms | 604 KB | Correct answer: answer = 764 |
9 | Correct | 1 ms | 472 KB | Correct answer: answer = 250000 |
10 | Correct | 1 ms | 348 KB | Correct answer: answer = 500 |
11 | Correct | 0 ms | 348 KB | Correct answer: answer = 32 |
12 | Correct | 1 ms | 348 KB | Correct answer: answer = 130050 |
13 | Correct | 5 ms | 388 KB | Correct answer: answer = 5110 |
14 | Correct | 1 ms | 344 KB | Correct answer: answer = 2626 |
15 | Correct | 3 ms | 536 KB | Correct answer: answer = 796 |
16 | Correct | 5 ms | 604 KB | Correct answer: answer = 7580 |
17 | Correct | 14 ms | 604 KB | Correct answer: answer = 1904 |
18 | Correct | 1 ms | 348 KB | Correct answer: answer = 996004 |
19 | Correct | 2 ms | 348 KB | Correct answer: answer = 38817 |
20 | Correct | 7 ms | 620 KB | Correct answer: answer = 4096 |
21 | Correct | 1 ms | 348 KB | Correct answer: answer = 1 |
22 | Correct | 0 ms | 348 KB | Correct answer: answer = 1 |
23 | Correct | 13 ms | 604 KB | Correct answer: answer = 2040 |
24 | Correct | 1 ms | 344 KB | Correct answer: answer = 2 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 348 KB | Wrong answer: output = 1, expected = 4 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 348 KB | Wrong answer: output = 1, expected = 4 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 348 KB | Wrong answer: output = 1, expected = 4 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 348 KB | Wrong answer: output = 1, expected = 4 |
2 | Halted | 0 ms | 0 KB | - |