# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
958046 |
2024-04-04T18:13:11 Z |
Lalic |
Aliens (IOI16_aliens) |
C++17 |
|
2 ms |
2420 KB |
#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5+10;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
vector<pll> interv;
for(int i=0;i<n;i++) interv.pb({r[i], c[i]});
for(int i=0;i<n;i++)
if(interv[i].fi>interv[i].se) swap(interv[i].fi, interv[i].se);
sort(all(interv), [&](pll a, pll b){ return (a.fi!=b.fi ? a.fi<b.fi : a.se>b.se); });
int last=-1;
vector<pll> proc; proc.pb({0, 0});
for(auto u : interv){
if(u.se<=last) continue;
proc.pb(u);
last=u.se;
}
//ll ans=0;
//for(auto u : proc) ans+=(u.se-u.fi+1ll)*(u.se-u.fi+1ll);
//return ans;
n=(int)proc.size()-1;
ll dp[505][505];
for(int i=0;i<=n;i++)
for(int j=0;j<=k;j++)
dp[i][j]=LINF;
dp[0][0]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
for(int w=0;w<i;w++){
if(dp[w][j-1]==LINF) continue;
ll val=dp[w][j-1]+(proc[i].se-proc[w+1].fi+1ll)*(proc[i].se-proc[w+1].fi+1ll);
if(w) val-=max((proc[w].se-proc[w+1].fi+1ll)*(proc[w].se-proc[w+1].fi+1ll), 0ll);
dp[i][j]=min(dp[i][j], val);
}
}
}
ll best=LINF;
for(int i=0;i<=k;i++) best=min(best, dp[n][i]);
return best;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 4 |
2 |
Correct |
1 ms |
2420 KB |
Correct answer: answer = 4 |
3 |
Correct |
2 ms |
2396 KB |
Correct answer: answer = 4 |
4 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 12 |
5 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 52 |
6 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 210 |
7 |
Correct |
2 ms |
2392 KB |
Correct answer: answer = 88 |
8 |
Correct |
1 ms |
2392 KB |
Correct answer: answer = 7696 |
9 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 1 |
10 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 2374 |
11 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 9502 |
12 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 49 |
13 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 151 |
14 |
Correct |
2 ms |
2396 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
2404 KB |
Correct answer: answer = 7550 |
17 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
2220 KB |
Correct answer: answer = 10000 |
19 |
Incorrect |
1 ms |
2396 KB |
Wrong answer: output = 559, expected = 624 |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2396 KB |
Correct answer: answer = 1 |
2 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
2392 KB |
Correct answer: answer = 1 |
4 |
Correct |
2 ms |
2396 KB |
Correct answer: answer = 5 |
5 |
Incorrect |
1 ms |
2396 KB |
Wrong answer: output = 21, expected = 41 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 4 |
2 |
Correct |
1 ms |
2420 KB |
Correct answer: answer = 4 |
3 |
Correct |
2 ms |
2396 KB |
Correct answer: answer = 4 |
4 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 12 |
5 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 52 |
6 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 210 |
7 |
Correct |
2 ms |
2392 KB |
Correct answer: answer = 88 |
8 |
Correct |
1 ms |
2392 KB |
Correct answer: answer = 7696 |
9 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 1 |
10 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 2374 |
11 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 9502 |
12 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 49 |
13 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 151 |
14 |
Correct |
2 ms |
2396 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
2404 KB |
Correct answer: answer = 7550 |
17 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
2220 KB |
Correct answer: answer = 10000 |
19 |
Incorrect |
1 ms |
2396 KB |
Wrong answer: output = 559, expected = 624 |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 4 |
2 |
Correct |
1 ms |
2420 KB |
Correct answer: answer = 4 |
3 |
Correct |
2 ms |
2396 KB |
Correct answer: answer = 4 |
4 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 12 |
5 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 52 |
6 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 210 |
7 |
Correct |
2 ms |
2392 KB |
Correct answer: answer = 88 |
8 |
Correct |
1 ms |
2392 KB |
Correct answer: answer = 7696 |
9 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 1 |
10 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 2374 |
11 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 9502 |
12 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 49 |
13 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 151 |
14 |
Correct |
2 ms |
2396 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
2404 KB |
Correct answer: answer = 7550 |
17 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
2220 KB |
Correct answer: answer = 10000 |
19 |
Incorrect |
1 ms |
2396 KB |
Wrong answer: output = 559, expected = 624 |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 4 |
2 |
Correct |
1 ms |
2420 KB |
Correct answer: answer = 4 |
3 |
Correct |
2 ms |
2396 KB |
Correct answer: answer = 4 |
4 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 12 |
5 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 52 |
6 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 210 |
7 |
Correct |
2 ms |
2392 KB |
Correct answer: answer = 88 |
8 |
Correct |
1 ms |
2392 KB |
Correct answer: answer = 7696 |
9 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 1 |
10 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 2374 |
11 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 9502 |
12 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 49 |
13 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 151 |
14 |
Correct |
2 ms |
2396 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
2404 KB |
Correct answer: answer = 7550 |
17 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
2220 KB |
Correct answer: answer = 10000 |
19 |
Incorrect |
1 ms |
2396 KB |
Wrong answer: output = 559, expected = 624 |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 4 |
2 |
Correct |
1 ms |
2420 KB |
Correct answer: answer = 4 |
3 |
Correct |
2 ms |
2396 KB |
Correct answer: answer = 4 |
4 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 12 |
5 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 52 |
6 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 210 |
7 |
Correct |
2 ms |
2392 KB |
Correct answer: answer = 88 |
8 |
Correct |
1 ms |
2392 KB |
Correct answer: answer = 7696 |
9 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 1 |
10 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 2374 |
11 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 9502 |
12 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 49 |
13 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 151 |
14 |
Correct |
2 ms |
2396 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
2404 KB |
Correct answer: answer = 7550 |
17 |
Correct |
1 ms |
2396 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
2220 KB |
Correct answer: answer = 10000 |
19 |
Incorrect |
1 ms |
2396 KB |
Wrong answer: output = 559, expected = 624 |
20 |
Halted |
0 ms |
0 KB |
- |