oj.uz

Submission #492301

# Submission time Handle Problem Language Result Execution time Memory
492301 2021-12-06T14:49:36 Z Killer2501 Aliens (IOI16_aliens) C++14
4 / 100
 2 ms 2752 KB 
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pll pair<ll, ll>
#define pb push_back
using namespace std;
const int N = 1e5+5;
const int M = 2e5+5;
const ll mod = 1e9+7;
const int base = 400;
const ll inf = 1e16;
ll ans, tong, n, k, a[N], b[N], m, t, dp[N][2];
vector<pll> adj[N], kq;
string s;
pll p[N], f[N], res;
void cal(int l, int r, int opl, int opr, int j)
{
    if(l > r)return;
    int mid = (l+r)/2;
    int best = mid;
    dp[mid][j] = inf;
    for(int i = opl; i <= min(mid, opr); i ++)
    {
        tong = dp[i-1][j^1] + (p[mid].se-p[i].fi+1)*(p[mid].se-p[i].fi+1);
        if(i > 1)tong -= max(0ll, p[i-1].se-p[i].fi+1)*max(0ll, p[i-1].se-p[i].fi+1);
        if(dp[mid][j] > tong)
        {
            dp[mid][j] = tong;
            best = i;
        }
    }
    cal(l, mid-1, opl, best, j);
    cal(mid+1, r, best, opr, j);
}
struct line
{
    ll a, b, id;
    line(){};
    line(ll _a, ll _b, ll _id)
    {
        a = _a;
        b = _b;
        id = _id;
    }
    ll f(ll x)
    {
        return a*x + b;
    }

};
struct Hull
{
    vector<line> q;
    int pos = 0;
    bool ccw(line x, line y, line z)
    {
        return x.a*(y.b-z.b) + y.a*(z.b-x.b) + z.a*(x.b-y.b) > 0;
    }
    void add(line d)
    {
        while(q.size() > 1 && !ccw(q[q.size()-2], q.back(), d))q.pop_back();
        if(!q.empty())pos = min(pos, (int)q.size()-1);
        q.pb(d);
    }
    pll get(ll x)
    {
        while(pos+1 < q.size() && q[pos].f(x) > q[pos+1].f(x))++pos;
        return {q[pos].f(x), q[pos].id};
    }
};

bool cmp(pll& x, pll& y)
{
    if(x.fi != y.fi)return x.fi < y.fi;
    return x.se > y.se;
}
pll check(ll pen)
{
    f[0] = {0, 0};
    Hull hull;
    for(int i = 1; i <= n; i ++)
    {
        tong = f[i-1].fi + p[i].fi*p[i].fi;
        if(i > 1)tong -= max(0ll, p[i-1].se-p[i].fi+1)*max(0ll, p[i-1].se-p[i].fi+1);
        hull.add(line(-2*p[i].fi, tong, f[i-1].se));
        f[i] = hull.get(p[i].se+1);
        f[i].fi += (p[i].se+1)*(p[i].se+1) + pen ;
        f[i].se += 1;
    }
    return f[n];
}
ll take_photos(int N, int M, int K, vector<int> r, vector<int> c)
{
    n = N;
    m = M;
    k = K;
    for(int i = 1; i <= n; i ++)
    {
        p[i].fi = r[i-1];
        p[i].se = c[i-1];
        if(p[i].fi > p[i].se)swap(p[i].fi, p[i].se);
    }
    sort(p+1, p+1+n, cmp);
    for(int i = 1; i <= n; i ++)
    {
        if(!kq.empty() && kq.back().se >= p[i].se)continue;
        kq.pb(p[i]);
    }
    n = kq.size();
    for(int i = 1; i <= n; i ++)p[i] = kq[i-1];
    ll lf = 0, rt = m*m, mid;
    while(lf <= rt)
    {
        mid = (lf+rt)/2;
        if(check(mid).se > k)lf = mid+1;
        else rt = mid-1;
    }
    res = check(lf);
    //cout << rt <<" "<<res.fi<<" "<<res.se <<" "<<k<<'\n';
    return res.fi - k*lf;
}
void sol()
{
    vector<int> r, c;
    cin >> n >> m >> k;
    r.resize(n);
    c.resize(n);
    for(int i = 0; i < n; i ++)cin >> r[i];
    for(int i = 0; i < n; i ++)cin >> c[i];
    cout << take_photos(n, m, k, r, c);
}

Compilation message

aliens.cpp: In member function 'std::pair<long long int, long long int> Hull::get(long long int)':
aliens.cpp:68:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         while(pos+1 < q.size() && q[pos].f(x) > q[pos+1].f(x))++pos;
      |               ~~~~~~^~~~~~~~~~

Subtask #1
4.0 / 4.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2592 KB Correct answer: answer = 1
2 Correct 1 ms 2636 KB Correct answer: answer = 4
3 Correct 1 ms 2636 KB Correct answer: answer = 1
4 Correct 1 ms 2636 KB Correct answer: answer = 5
5 Incorrect 1 ms 2636 KB Wrong answer: output = 83, expected = 41
6 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Correct answer: answer = 4
2 Correct 1 ms 2636 KB Correct answer: answer = 4
3 Correct 1 ms 2636 KB Correct answer: answer = 4
4 Correct 1 ms 2636 KB Correct answer: answer = 12
5 Correct 1 ms 2636 KB Correct answer: answer = 52
6 Correct 1 ms 2636 KB Correct answer: answer = 210
7 Correct 1 ms 2636 KB Correct answer: answer = 88
8 Correct 2 ms 2636 KB Correct answer: answer = 7696
9 Correct 1 ms 2636 KB Correct answer: answer = 1
10 Correct 1 ms 2636 KB Correct answer: answer = 2374
11 Correct 1 ms 2568 KB Correct answer: answer = 9502
12 Correct 1 ms 2636 KB Correct answer: answer = 49
13 Correct 1 ms 2636 KB Correct answer: answer = 151
14 Correct 1 ms 2636 KB Correct answer: answer = 7550
15 Correct 1 ms 2636 KB Correct answer: answer = 7220
16 Correct 1 ms 2636 KB Correct answer: answer = 7550
17 Correct 1 ms 2636 KB Correct answer: answer = 10000
18 Correct 1 ms 2636 KB Correct answer: answer = 10000
19 Correct 1 ms 2636 KB Correct answer: answer = 624
20 Correct 2 ms 2752 KB Correct answer: answer = 10000
21 Correct 1 ms 2592 KB Correct answer: answer = 1
22 Correct 1 ms 2636 KB Correct answer: answer = 4
23 Correct 1 ms 2636 KB Correct answer: answer = 1
24 Correct 1 ms 2636 KB Correct answer: answer = 5
25 Incorrect 1 ms 2636 KB Wrong answer: output = 83, expected = 41
26 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Correct answer: answer = 4
2 Correct 1 ms 2636 KB Correct answer: answer = 4
3 Correct 1 ms 2636 KB Correct answer: answer = 4
4 Correct 1 ms 2636 KB Correct answer: answer = 12
5 Correct 1 ms 2636 KB Correct answer: answer = 52
6 Correct 1 ms 2636 KB Correct answer: answer = 210
7 Correct 1 ms 2636 KB Correct answer: answer = 88
8 Correct 2 ms 2636 KB Correct answer: answer = 7696
9 Correct 1 ms 2636 KB Correct answer: answer = 1
10 Correct 1 ms 2636 KB Correct answer: answer = 2374
11 Correct 1 ms 2568 KB Correct answer: answer = 9502
12 Correct 1 ms 2636 KB Correct answer: answer = 49
13 Correct 1 ms 2636 KB Correct answer: answer = 151
14 Correct 1 ms 2636 KB Correct answer: answer = 7550
15 Correct 1 ms 2636 KB Correct answer: answer = 7220
16 Correct 1 ms 2636 KB Correct answer: answer = 7550
17 Correct 1 ms 2636 KB Correct answer: answer = 10000
18 Correct 1 ms 2636 KB Correct answer: answer = 10000
19 Correct 1 ms 2636 KB Correct answer: answer = 624
20 Correct 2 ms 2752 KB Correct answer: answer = 10000
21 Correct 1 ms 2592 KB Correct answer: answer = 1
22 Correct 1 ms 2636 KB Correct answer: answer = 4
23 Correct 1 ms 2636 KB Correct answer: answer = 1
24 Correct 1 ms 2636 KB Correct answer: answer = 5
25 Incorrect 1 ms 2636 KB Wrong answer: output = 83, expected = 41
26 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Correct answer: answer = 4
2 Correct 1 ms 2636 KB Correct answer: answer = 4
3 Correct 1 ms 2636 KB Correct answer: answer = 4
4 Correct 1 ms 2636 KB Correct answer: answer = 12
5 Correct 1 ms 2636 KB Correct answer: answer = 52
6 Correct 1 ms 2636 KB Correct answer: answer = 210
7 Correct 1 ms 2636 KB Correct answer: answer = 88
8 Correct 2 ms 2636 KB Correct answer: answer = 7696
9 Correct 1 ms 2636 KB Correct answer: answer = 1
10 Correct 1 ms 2636 KB Correct answer: answer = 2374
11 Correct 1 ms 2568 KB Correct answer: answer = 9502
12 Correct 1 ms 2636 KB Correct answer: answer = 49
13 Correct 1 ms 2636 KB Correct answer: answer = 151
14 Correct 1 ms 2636 KB Correct answer: answer = 7550
15 Correct 1 ms 2636 KB Correct answer: answer = 7220
16 Correct 1 ms 2636 KB Correct answer: answer = 7550
17 Correct 1 ms 2636 KB Correct answer: answer = 10000
18 Correct 1 ms 2636 KB Correct answer: answer = 10000
19 Correct 1 ms 2636 KB Correct answer: answer = 624
20 Correct 2 ms 2752 KB Correct answer: answer = 10000
21 Correct 1 ms 2592 KB Correct answer: answer = 1
22 Correct 1 ms 2636 KB Correct answer: answer = 4
23 Correct 1 ms 2636 KB Correct answer: answer = 1
24 Correct 1 ms 2636 KB Correct answer: answer = 5
25 Incorrect 1 ms 2636 KB Wrong answer: output = 83, expected = 41
26 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Correct answer: answer = 4
2 Correct 1 ms 2636 KB Correct answer: answer = 4
3 Correct 1 ms 2636 KB Correct answer: answer = 4
4 Correct 1 ms 2636 KB Correct answer: answer = 12
5 Correct 1 ms 2636 KB Correct answer: answer = 52
6 Correct 1 ms 2636 KB Correct answer: answer = 210
7 Correct 1 ms 2636 KB Correct answer: answer = 88
8 Correct 2 ms 2636 KB Correct answer: answer = 7696
9 Correct 1 ms 2636 KB Correct answer: answer = 1
10 Correct 1 ms 2636 KB Correct answer: answer = 2374
11 Correct 1 ms 2568 KB Correct answer: answer = 9502
12 Correct 1 ms 2636 KB Correct answer: answer = 49
13 Correct 1 ms 2636 KB Correct answer: answer = 151
14 Correct 1 ms 2636 KB Correct answer: answer = 7550
15 Correct 1 ms 2636 KB Correct answer: answer = 7220
16 Correct 1 ms 2636 KB Correct answer: answer = 7550
17 Correct 1 ms 2636 KB Correct answer: answer = 10000
18 Correct 1 ms 2636 KB Correct answer: answer = 10000
19 Correct 1 ms 2636 KB Correct answer: answer = 624
20 Correct 2 ms 2752 KB Correct answer: answer = 10000
21 Correct 1 ms 2592 KB Correct answer: answer = 1
22 Correct 1 ms 2636 KB Correct answer: answer = 4
23 Correct 1 ms 2636 KB Correct answer: answer = 1
24 Correct 1 ms 2636 KB Correct answer: answer = 5
25 Incorrect 1 ms 2636 KB Wrong answer: output = 83, expected = 41
26 Halted 0 ms 0 KB -