oj.uz

Submission #43841

# Submission time Handle Problem Language Result Execution time Memory
43841 2018-03-25T11:20:32 Z PowerOfNinjaGo Aliens (IOI16_aliens) C++14
0 / 100
 422 ms 94576 KB 
//Power Of Ninja Go
#include <bits/stdc++.h>
#ifdef atom
    #include "grader.cpp"
#else
    #include "aliens.h"
#endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii;
#define X first
#define Y second
#define vi vector<int>
#define vii vector< ii >
#define pb push_back
struct line
{
    ll m, b;
    int k;
    line()
    {
        m = 0, b = 2e18; k = 0;
    }
    line(ll _m, ll _b, int _k)
    {
        m = _m; b = _b; k = _k;
    }
    ll f(int x){ return m*x+b; }
};
bool lessthan(line A, line B, int x)
{
    ll y1 = A.f(x), y2 = B.f(x);
    if(y1 != y2) return y1< y2;
    return A.k< B.k;
}
const int maxn = 1e5+5;
const int maxm = 1e6+5;
int n, m;
line st[4*maxm];
ll dp[maxn];
int opt[maxn];
void add(line t, int p = 1, int L = 0, int R = m-1)
{
    int M = (L+R)/2;
    bool lef = t.f(L) < st[p].f(L);
    bool mid = t.f(M) < st[p].f(M);
    if(mid) swap(t, st[p]);
    if(L == R) return;
    if(lef != mid) add(t, 2*p, L, M);
    else add(t, 2*p+1, M+1, R);
}
line ask(int x, int p = 1, int L = 0, int R = m-1)
{
    if(L == R) return st[p];
    int M = (L+R)/2;
    line h = st[p];
    line o;
    if(x<= M) o = ask(x, 2*p, L, M);
    else o = ask(x, 2*p+1, M+1, R);
    if(lessthan(h, o, x)) return h;
    return o;
}
vii vec, tmp;
vi r, c;
bool cmp(ii A, ii B)
{
    if(A.X != B.X) return A.X< B.X;
    return A.Y> B.Y;
}
pair<long long, int> trial(ll lambda)
{
    for(int i = 1; i< 4*maxm; i++) st[i] = line();
    add(line(-2LL*r[0], 1LL*r[0]*r[0]-2*r[0], 0));
    for(int i = 0; i< n; i++)
    {
        line res = ask(c[i]);
        //printf("use line %lld %lld\n", res.m, res.b);
        opt[i] = res.k+1;
        dp[i] = res.f(c[i])+1LL*c[i]*c[i]+2*c[i]+lambda+1;
        //printf("dp[%d] = %lld\n", i, dp[i]);
        //if(i+1< n) printf("push m = %lld b = %lld\n", -2LL*r[i+1], dp[i]+1LL*r[i+1]*r[i+1]-2*r[i+1]);
        if(i+1< n) add(line(-2LL*r[i+1], dp[i]+1LL*r[i+1]*r[i+1]-2*r[i+1], opt[i]));
    }
    return make_pair(dp[n-1], opt[n-1]);
}
long long take_photos(int N, int M, int K, std::vector<int> R, std::vector<int> C)
{
    n = N; m = M;
    for(int i = 0; i< n; i++)
    {
        if(R[i]<= C[i]) vec.pb(ii(R[i], C[i]));
        else vec.pb(ii(C[i], R[i]));
    }
    tmp = vec;
    vec.clear();
    sort(tmp.begin(), tmp.end(), cmp);
    for(auto k : tmp)
    {
        if(vec.empty() || k.Y> vec.back().Y) vec.pb(k);
    }
    n = vec.size();
    for(int i = 0; i< n; i++) r.pb(vec[i].X), c.pb(vec[i].Y);
    //for(int i = 0; i< n; i++) printf("%d %d\n", r[i], c[i]);
    //printf("0: %lld %d\n", trial(0).X, trial(0).Y);
    ll lo = 0, hi = 1LL*m*m;
    // while(lo< hi)
    // {
    //     ll mid = (lo+hi+1)/2;
    //     auto res = trial(mid);
    //     //printf("%lld: (%lld %d)\n", mid, res.X, res.Y);
    //     if(res.Y>= K) lo = mid;
    //     else hi = mid-1;
    // }
    // return trial(lo).X-1LL*K*lo;
    ll best = 2e18;
    for(int i = 0; i<= m*m; i++)
    {
        best = min(best, trial(i).X);
    }
    return best;
}

Compilation message

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:104:8: warning: unused variable 'lo' [-Wunused-variable]
     ll lo = 0, hi = 1LL*m*m;
        ^
aliens.cpp:104:16: warning: unused variable 'hi' [-Wunused-variable]
     ll lo = 0, hi = 1LL*m*m;
                ^

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 94328 KB Correct answer: answer = 4
2 Correct 172 ms 94408 KB Correct answer: answer = 4
3 Correct 276 ms 94408 KB Correct answer: answer = 4
4 Incorrect 422 ms 94576 KB Wrong answer: output = 13, expected = 12
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 94576 KB Correct answer: answer = 1
2 Incorrect 169 ms 94576 KB Wrong answer: output = 2, expected = 4
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 94328 KB Correct answer: answer = 4
2 Correct 172 ms 94408 KB Correct answer: answer = 4
3 Correct 276 ms 94408 KB Correct answer: answer = 4
4 Incorrect 422 ms 94576 KB Wrong answer: output = 13, expected = 12
5 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 94328 KB Correct answer: answer = 4
2 Correct 172 ms 94408 KB Correct answer: answer = 4
3 Correct 276 ms 94408 KB Correct answer: answer = 4
4 Incorrect 422 ms 94576 KB Wrong answer: output = 13, expected = 12
5 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 94328 KB Correct answer: answer = 4
2 Correct 172 ms 94408 KB Correct answer: answer = 4
3 Correct 276 ms 94408 KB Correct answer: answer = 4
4 Incorrect 422 ms 94576 KB Wrong answer: output = 13, expected = 12
5 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 94328 KB Correct answer: answer = 4
2 Correct 172 ms 94408 KB Correct answer: answer = 4
3 Correct 276 ms 94408 KB Correct answer: answer = 4
4 Incorrect 422 ms 94576 KB Wrong answer: output = 13, expected = 12
5 Halted 0 ms 0 KB -