oj.uz

Submission #416518

# Submission time Handle Problem Language Result Execution time Memory
416518 2021-06-02T14:16:54 Z Aldas25 Aliens (IOI16_aliens) C++14
4 / 100
 1211 ms 352 KB 
#include "aliens.h"
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int MAXN = 100100;
const ll INF = 1e13;

pii norm (int r, int c) {
    if (r <= c) return {r,c};
    return {c, r};
}

bool cmp (pii a, pii b) {
    return a.f + a.s < b.f + b.s;
}

vii seq;
int n;
ll dp[MAXN], fr[MAXN], to[MAXN], cnt[MAXN];
ll r[MAXN], c[MAXN];

pair<ll, ll> kvadrat (int a, int b) {
    ll mn = r[a], mx = c[a];
    FOR(i, a, b) {
        mn = min(mn, r[i]);
        mx = max(mx, c[i]);
    }
    return {mn, mx};
}

ll kvadratArea (pair<ll, ll> a) {
    ll krast = a.s - a.f + 1;
    return (krast*krast);
}

ll intersection (pair<ll, ll> a, pair<ll, ll> b) {
    if (a.f > b.f) swap(a,b);
    //if (a.f == b.f && a.s > b.s) swap(a,b);
    if (b.s <= a.s) {
        /// inside one another
        return kvadratArea({b.f, b.s});
    }

    if (a.s < b.f) return 0;
    //cout << "             intersection between (" << a.f << ", " << a.s << ") and ("
    //<< b.f << ", " << b.s << ")    is: (" << b.f << ", " << a.s << ")" <<endl;
    return kvadratArea({b.f, a.s});
}

void solve (ll lambda) {
   // cout << " lambda = " << lambda << endl;
    FOR(i, 0, n-1) {
        auto kvv = kvadrat(0, i);
        dp[i] = kvadratArea(kvv) + lambda;
        cnt[i] = 1;
        fr[i] = kvv.f, to[i] = kvv.s;

        if (i == 0) {
            //cout << "     i = " << i << " r = " << r[i] <<" c = " << c[i] << " dp = " << dp[i] << " (in cont)" << endl;
            continue;
        }
        FOR(j, 0, i-1) {
            auto kv = kvadrat(j+1, i);
            ll cur = dp[j] + kvadratArea(kv) - intersection(kv, {fr[j], to[j]});
            cur += lambda;
            if (cur < dp[i]) {
                dp[i] = cur;
                fr[i] = kv.f, to[i] = kv.s;
                cnt[i] = cnt[j] + 1;
            }

           // cout << "   i = " << i << " j = " << j << " cur =" << cur << endl;
           // cout << "      kv = (" << kv.f << ", " << kv.s << "),   kvadratArea: " <<
           // kvadratArea(kv) << "  intersection: " << intersection(kv, {fr[j], to[j]}) << endl;
        }

        //cout << "     i = " << i << " r = " << r[i] <<" c = " << c[i] << " dp = " << dp[i]
         //<< "   cnt = " << cnt[i] << " fr = " << fr[i] << " to = " << to[i] << endl;
    }
}

long long take_photos(int N, int m, int k, std::vector<int> R, std::vector<int> C) {

    n = N;

    FOR(i, 0, n-1) {
        seq.pb(norm(R[i], C[i]));
    }
    sort(seq.begin(), seq.end(), cmp);
    FOR(i, 0, n-1) r[i] = seq[i].f, c[i] = seq[i].s;

    ll le = 0, ri = INF;
    while (le < ri) {
        ll mid = (le+ri)/2;
        solve (mid);
        if (cnt[n-1] <= k) ri = mid;
        else le = mid+1;
    }
    solve (le);
    ll ans = dp[n-1] - cnt[n-1]*le;

    return ans;
}

/*
5 7 2
0 3
4 4
4 6
4 5
4 6
ans: 25

2 6 2
1 4
4 1
ans: 16


5 5 5
1 1
3 4
4 1
3 1
3 0
ans: 23
*/

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Correct answer: answer = 4
2 Correct 1 ms 204 KB Correct answer: answer = 4
3 Correct 1 ms 332 KB Correct answer: answer = 4
4 Correct 1 ms 332 KB Correct answer: answer = 12
5 Correct 1 ms 332 KB Correct answer: answer = 52
6 Correct 1 ms 332 KB Correct answer: answer = 210
7 Correct 1 ms 332 KB Correct answer: answer = 88
8 Correct 1 ms 204 KB Correct answer: answer = 7696
9 Correct 2 ms 204 KB Correct answer: answer = 1
10 Correct 2 ms 204 KB Correct answer: answer = 2374
11 Correct 2 ms 304 KB Correct answer: answer = 9502
12 Correct 2 ms 204 KB Correct answer: answer = 49
13 Correct 2 ms 204 KB Correct answer: answer = 151
14 Correct 2 ms 204 KB Correct answer: answer = 7550
15 Correct 2 ms 204 KB Correct answer: answer = 7220
16 Correct 3 ms 332 KB Correct answer: answer = 7550
17 Correct 2 ms 204 KB Correct answer: answer = 10000
18 Correct 2 ms 296 KB Correct answer: answer = 10000
19 Correct 2 ms 332 KB Correct answer: answer = 624
20 Correct 2 ms 332 KB Correct answer: answer = 10000

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Correct answer: answer = 1
2 Correct 0 ms 204 KB Correct answer: answer = 4
3 Correct 1 ms 204 KB Correct answer: answer = 1
4 Correct 0 ms 204 KB Correct answer: answer = 5
5 Correct 1 ms 204 KB Correct answer: answer = 41
6 Correct 1 ms 204 KB Correct answer: answer = 71923
7 Correct 83 ms 332 KB Correct answer: answer = 77137
8 Incorrect 1211 ms 352 KB Wrong answer: output = 925, expected = 764
9 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Correct answer: answer = 4
2 Correct 1 ms 204 KB Correct answer: answer = 4
3 Correct 1 ms 332 KB Correct answer: answer = 4
4 Correct 1 ms 332 KB Correct answer: answer = 12
5 Correct 1 ms 332 KB Correct answer: answer = 52
6 Correct 1 ms 332 KB Correct answer: answer = 210
7 Correct 1 ms 332 KB Correct answer: answer = 88
8 Correct 1 ms 204 KB Correct answer: answer = 7696
9 Correct 2 ms 204 KB Correct answer: answer = 1
10 Correct 2 ms 204 KB Correct answer: answer = 2374
11 Correct 2 ms 304 KB Correct answer: answer = 9502
12 Correct 2 ms 204 KB Correct answer: answer = 49
13 Correct 2 ms 204 KB Correct answer: answer = 151
14 Correct 2 ms 204 KB Correct answer: answer = 7550
15 Correct 2 ms 204 KB Correct answer: answer = 7220
16 Correct 3 ms 332 KB Correct answer: answer = 7550
17 Correct 2 ms 204 KB Correct answer: answer = 10000
18 Correct 2 ms 296 KB Correct answer: answer = 10000
19 Correct 2 ms 332 KB Correct answer: answer = 624
20 Correct 2 ms 332 KB Correct answer: answer = 10000
21 Correct 0 ms 204 KB Correct answer: answer = 1
22 Correct 0 ms 204 KB Correct answer: answer = 4
23 Correct 1 ms 204 KB Correct answer: answer = 1
24 Correct 0 ms 204 KB Correct answer: answer = 5
25 Correct 1 ms 204 KB Correct answer: answer = 41
26 Correct 1 ms 204 KB Correct answer: answer = 71923
27 Correct 83 ms 332 KB Correct answer: answer = 77137
28 Incorrect 1211 ms 352 KB Wrong answer: output = 925, expected = 764
29 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Correct answer: answer = 4
2 Correct 1 ms 204 KB Correct answer: answer = 4
3 Correct 1 ms 332 KB Correct answer: answer = 4
4 Correct 1 ms 332 KB Correct answer: answer = 12
5 Correct 1 ms 332 KB Correct answer: answer = 52
6 Correct 1 ms 332 KB Correct answer: answer = 210
7 Correct 1 ms 332 KB Correct answer: answer = 88
8 Correct 1 ms 204 KB Correct answer: answer = 7696
9 Correct 2 ms 204 KB Correct answer: answer = 1
10 Correct 2 ms 204 KB Correct answer: answer = 2374
11 Correct 2 ms 304 KB Correct answer: answer = 9502
12 Correct 2 ms 204 KB Correct answer: answer = 49
13 Correct 2 ms 204 KB Correct answer: answer = 151
14 Correct 2 ms 204 KB Correct answer: answer = 7550
15 Correct 2 ms 204 KB Correct answer: answer = 7220
16 Correct 3 ms 332 KB Correct answer: answer = 7550
17 Correct 2 ms 204 KB Correct answer: answer = 10000
18 Correct 2 ms 296 KB Correct answer: answer = 10000
19 Correct 2 ms 332 KB Correct answer: answer = 624
20 Correct 2 ms 332 KB Correct answer: answer = 10000
21 Correct 0 ms 204 KB Correct answer: answer = 1
22 Correct 0 ms 204 KB Correct answer: answer = 4
23 Correct 1 ms 204 KB Correct answer: answer = 1
24 Correct 0 ms 204 KB Correct answer: answer = 5
25 Correct 1 ms 204 KB Correct answer: answer = 41
26 Correct 1 ms 204 KB Correct answer: answer = 71923
27 Correct 83 ms 332 KB Correct answer: answer = 77137
28 Incorrect 1211 ms 352 KB Wrong answer: output = 925, expected = 764
29 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Correct answer: answer = 4
2 Correct 1 ms 204 KB Correct answer: answer = 4
3 Correct 1 ms 332 KB Correct answer: answer = 4
4 Correct 1 ms 332 KB Correct answer: answer = 12
5 Correct 1 ms 332 KB Correct answer: answer = 52
6 Correct 1 ms 332 KB Correct answer: answer = 210
7 Correct 1 ms 332 KB Correct answer: answer = 88
8 Correct 1 ms 204 KB Correct answer: answer = 7696
9 Correct 2 ms 204 KB Correct answer: answer = 1
10 Correct 2 ms 204 KB Correct answer: answer = 2374
11 Correct 2 ms 304 KB Correct answer: answer = 9502
12 Correct 2 ms 204 KB Correct answer: answer = 49
13 Correct 2 ms 204 KB Correct answer: answer = 151
14 Correct 2 ms 204 KB Correct answer: answer = 7550
15 Correct 2 ms 204 KB Correct answer: answer = 7220
16 Correct 3 ms 332 KB Correct answer: answer = 7550
17 Correct 2 ms 204 KB Correct answer: answer = 10000
18 Correct 2 ms 296 KB Correct answer: answer = 10000
19 Correct 2 ms 332 KB Correct answer: answer = 624
20 Correct 2 ms 332 KB Correct answer: answer = 10000
21 Correct 0 ms 204 KB Correct answer: answer = 1
22 Correct 0 ms 204 KB Correct answer: answer = 4
23 Correct 1 ms 204 KB Correct answer: answer = 1
24 Correct 0 ms 204 KB Correct answer: answer = 5
25 Correct 1 ms 204 KB Correct answer: answer = 41
26 Correct 1 ms 204 KB Correct answer: answer = 71923
27 Correct 83 ms 332 KB Correct answer: answer = 77137
28 Incorrect 1211 ms 352 KB Wrong answer: output = 925, expected = 764
29 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Correct answer: answer = 4
2 Correct 1 ms 204 KB Correct answer: answer = 4
3 Correct 1 ms 332 KB Correct answer: answer = 4
4 Correct 1 ms 332 KB Correct answer: answer = 12
5 Correct 1 ms 332 KB Correct answer: answer = 52
6 Correct 1 ms 332 KB Correct answer: answer = 210
7 Correct 1 ms 332 KB Correct answer: answer = 88
8 Correct 1 ms 204 KB Correct answer: answer = 7696
9 Correct 2 ms 204 KB Correct answer: answer = 1
10 Correct 2 ms 204 KB Correct answer: answer = 2374
11 Correct 2 ms 304 KB Correct answer: answer = 9502
12 Correct 2 ms 204 KB Correct answer: answer = 49
13 Correct 2 ms 204 KB Correct answer: answer = 151
14 Correct 2 ms 204 KB Correct answer: answer = 7550
15 Correct 2 ms 204 KB Correct answer: answer = 7220
16 Correct 3 ms 332 KB Correct answer: answer = 7550
17 Correct 2 ms 204 KB Correct answer: answer = 10000
18 Correct 2 ms 296 KB Correct answer: answer = 10000
19 Correct 2 ms 332 KB Correct answer: answer = 624
20 Correct 2 ms 332 KB Correct answer: answer = 10000
21 Correct 0 ms 204 KB Correct answer: answer = 1
22 Correct 0 ms 204 KB Correct answer: answer = 4
23 Correct 1 ms 204 KB Correct answer: answer = 1
24 Correct 0 ms 204 KB Correct answer: answer = 5
25 Correct 1 ms 204 KB Correct answer: answer = 41
26 Correct 1 ms 204 KB Correct answer: answer = 71923
27 Correct 83 ms 332 KB Correct answer: answer = 77137
28 Incorrect 1211 ms 352 KB Wrong answer: output = 925, expected = 764
29 Halted 0 ms 0 KB -