# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
382354 | 2021-03-27T07:06:56 Z | kshitij_sodani | Aliens (IOI16_aliens) | C++14 | 162 ms | 4332 KB |
//#pragma GCC optimize("Ofast,unroll-loops") #include <bits/stdc++.h> using namespace std; typedef long long llo; #define mp make_pair #define pb push_back #define a first #define b second #define xx int //#define endl '\n' #include "aliens.h" int mi[1000001]; llo dp[4001][4001]; long long take_photos(xx n, xx m, xx k,vector<xx> aa,vector<xx> bb) { vector<pair<llo,llo>> ss; for(llo i=0;i<m;i++){ mi[i]=-1; } for(llo i=0;i<n;i++){ mi[min(aa[i],bb[i])]=max(mi[min(aa[i],bb[i])],max(aa[i],bb[i])); } llo cur=-1; for(llo i=0;i<m;i++){ if(mi[i]!=-1){ if(mi[i]>cur){ ss.pb({i,mi[i]}); cur=mi[i]; } } } for(llo i=1;i<=k;i++){ for(llo j=0;j<ss.size();j++){ dp[j][i]=(ss[j].b-ss[0].a+1); dp[j][i]*=dp[j][i]; if(i==1){ continue; } for(llo ii=0;ii<j;ii++){ llo cur=max(ss[ii].b+1-ss[j].a,(llo)0); cur*=cur; dp[j][i]=min(dp[j][i],dp[ii][i-1]+(ss[j].b-ss[ii+1].a+1)*(ss[j].b-ss[ii+1].a+1)+cur); } } } /* cout<<dp[0][1]<<"::"<<dp[1][1]<<endl; for(auto j:ss){ cout<<j.a<<":"<<j.b<<endl; } cout<<endl;*/ return dp[ss.size()-1][k]; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Correct answer: answer = 4 |
2 | Correct | 1 ms | 364 KB | Correct answer: answer = 4 |
3 | Correct | 1 ms | 364 KB | Correct answer: answer = 4 |
4 | Incorrect | 1 ms | 364 KB | Wrong answer: output = 14, expected = 12 |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 492 KB | Correct answer: answer = 1 |
2 | Correct | 1 ms | 364 KB | Correct answer: answer = 4 |
3 | Correct | 1 ms | 364 KB | Correct answer: answer = 1 |
4 | Correct | 1 ms | 364 KB | Correct answer: answer = 5 |
5 | Correct | 1 ms | 364 KB | Correct answer: answer = 41 |
6 | Correct | 1 ms | 364 KB | Correct answer: answer = 71923 |
7 | Correct | 2 ms | 1132 KB | Correct answer: answer = 77137 |
8 | Correct | 51 ms | 2796 KB | Correct answer: answer = 764 |
9 | Correct | 2 ms | 2412 KB | Correct answer: answer = 250000 |
10 | Correct | 162 ms | 4332 KB | Correct answer: answer = 500 |
11 | Correct | 1 ms | 364 KB | Correct answer: answer = 32 |
12 | Correct | 2 ms | 2412 KB | Correct answer: answer = 130050 |
13 | Correct | 18 ms | 2540 KB | Correct answer: answer = 5110 |
14 | Correct | 4 ms | 1388 KB | Correct answer: answer = 2626 |
15 | Correct | 8 ms | 1516 KB | Correct answer: answer = 796 |
16 | Correct | 13 ms | 2540 KB | Correct answer: answer = 7580 |
17 | Correct | 55 ms | 2924 KB | Correct answer: answer = 1904 |
18 | Correct | 3 ms | 1900 KB | Correct answer: answer = 996004 |
19 | Correct | 6 ms | 2028 KB | Correct answer: answer = 38817 |
20 | Correct | 24 ms | 2284 KB | Correct answer: answer = 4096 |
21 | Correct | 1 ms | 364 KB | Correct answer: answer = 1 |
22 | Correct | 1 ms | 364 KB | Correct answer: answer = 1 |
23 | Correct | 41 ms | 2796 KB | Correct answer: answer = 2040 |
24 | Correct | 1 ms | 364 KB | Correct answer: answer = 2 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Correct answer: answer = 4 |
2 | Correct | 1 ms | 364 KB | Correct answer: answer = 4 |
3 | Correct | 1 ms | 364 KB | Correct answer: answer = 4 |
4 | Incorrect | 1 ms | 364 KB | Wrong answer: output = 14, expected = 12 |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Correct answer: answer = 4 |
2 | Correct | 1 ms | 364 KB | Correct answer: answer = 4 |
3 | Correct | 1 ms | 364 KB | Correct answer: answer = 4 |
4 | Incorrect | 1 ms | 364 KB | Wrong answer: output = 14, expected = 12 |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Correct answer: answer = 4 |
2 | Correct | 1 ms | 364 KB | Correct answer: answer = 4 |
3 | Correct | 1 ms | 364 KB | Correct answer: answer = 4 |
4 | Incorrect | 1 ms | 364 KB | Wrong answer: output = 14, expected = 12 |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Correct answer: answer = 4 |
2 | Correct | 1 ms | 364 KB | Correct answer: answer = 4 |
3 | Correct | 1 ms | 364 KB | Correct answer: answer = 4 |
4 | Incorrect | 1 ms | 364 KB | Wrong answer: output = 14, expected = 12 |
5 | Halted | 0 ms | 0 KB | - |