# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
958042 |
2024-04-04T18:07:55 Z |
Lalic |
Aliens (IOI16_aliens) |
C++17 |
|
0 ms |
348 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;
//dp[i][j]=min(dp[i][j], dp[w][j-1]+(proc[i].se-proc[w+1].fi+1ll)*(proc[i].se-proc[w+1].fi+1ll));
//}
//}
//}
//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 |
Incorrect |
0 ms |
344 KB |
Wrong answer: output = 5, expected = 4 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Wrong answer: output = 2, expected = 1 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Wrong answer: output = 5, expected = 4 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Wrong answer: output = 5, expected = 4 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Wrong answer: output = 5, expected = 4 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Wrong answer: output = 5, expected = 4 |
2 |
Halted |
0 ms |
0 KB |
- |