oj.uz

Submission #43044

# Submission time Handle Problem Language Result Execution time Memory
43044 2018-03-08T08:57:23 Z top34051 Aliens (IOI16_aliens) C++14
4 / 100
 3 ms 2224 KB 
#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll,ll>
#define X first
#define Y second
const int maxn = 1e5 + 5;
 
struct line {
    ll m,c;
    line(ll _m = 0, ll _c = 0) {
        m = _m; c = _c;
    }
};
 
int n,m,k;
pii p[maxn];
int r[maxn], c[maxn];
ll dp[maxn][2];
line cht[maxn];
 
bool cmp(pii x, pii y) {
    if(x.X!=y.X) return x.X<y.X;
    return x.Y>y.Y;
}
 
ll p2(ll x) { return x*x; }
 
double cut(int x, int y) {
    if(x==0 || y==0) return -2e16;
    return (double)(cht[y].c-cht[x].c)/(cht[x].m-cht[y].m);
}

bool bad(int x, int y, int z) {
    return 1LL*(cht[z].c-cht[x].c)*(cht[z].m-cht[y].m) > 1LL*(cht[z].c-cht[y].c)*(cht[x].m-cht[z].m);
}
 
void solve() {
    for(int x=1;x<=n;x++) dp[x][0] = 1e13;
    for(int t=1;t<=k;t++) {
        int len = 0;
        for(int x=1;x<=n;x++) {
            cht[++len] = line(-2*r[x], p2(r[x]) + dp[x-1][!(t&1)] - p2(max(0,c[x-1]-r[x])));
            while(len>=3 && bad(len-2,len-1,len)) cht[len-1] = cht[len], len--;
            int l = 2, r = len, mid, pos = 1;
            while(l<=r) {
                int mid = (l+r)/2;
                if(cut(mid-1,mid)<=c[x]) pos = mid, l = mid+1;
                else r = mid-1;
            }
            dp[x][t&1] = cht[pos].m*c[x] + cht[pos].c + p2(c[x]);
//            printf("dp %d %d = %lld\n",x,t,dp[x][t]);
        }
    }
}
 
long long take_photos(int N, int M, int K, std::vector<int> R, std::vector<int> C) {
	n = N; m = M; k = K;
	//prep
	for(int i=0;i<n;i++) {
        p[i] = {R[i],C[i]};
        if(p[i].X>p[i].Y) swap(p[i].X,p[i].Y);
	}
	sort(p,p+n,cmp);
    ll cur = -1, sz = 0;
	for(int i=0;i<n;i++) {
        if(p[i].Y<=cur) continue;
        sz++;
        r[sz] = p[i].X; c[sz] = p[i].Y+1;
        cur = p[i].Y;
	}
	n = sz;
	solve();
    return dp[n][k&1];
}

Compilation message

aliens.cpp: In function 'void solve()':
aliens.cpp:47:33: warning: unused variable 'mid' [-Wunused-variable]
             int l = 2, r = len, mid, pos = 1;
                                 ^

Subtask #1
4.0 / 4.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2224 KB Correct answer: answer = 1
2 Correct 3 ms 2224 KB Correct answer: answer = 4
3 Correct 2 ms 2224 KB Correct answer: answer = 1
4 Correct 2 ms 2224 KB Correct answer: answer = 5
5 Correct 2 ms 2224 KB Correct answer: answer = 41
6 Incorrect 3 ms 2224 KB Wrong answer: output = 84130, expected = 71923
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1908 KB Correct answer: answer = 4
2 Correct 2 ms 1992 KB Correct answer: answer = 4
3 Correct 2 ms 2064 KB Correct answer: answer = 4
4 Correct 2 ms 2064 KB Correct answer: answer = 12
5 Correct 2 ms 2064 KB Correct answer: answer = 52
6 Correct 2 ms 2064 KB Correct answer: answer = 210
7 Correct 2 ms 2068 KB Correct answer: answer = 88
8 Correct 2 ms 2068 KB Correct answer: answer = 7696
9 Correct 2 ms 2068 KB Correct answer: answer = 1
10 Correct 3 ms 2068 KB Correct answer: answer = 2374
11 Correct 2 ms 2068 KB Correct answer: answer = 9502
12 Correct 2 ms 2068 KB Correct answer: answer = 49
13 Correct 2 ms 2084 KB Correct answer: answer = 151
14 Correct 2 ms 2084 KB Correct answer: answer = 7550
15 Correct 2 ms 2084 KB Correct answer: answer = 7220
16 Correct 3 ms 2084 KB Correct answer: answer = 7550
17 Correct 3 ms 2084 KB Correct answer: answer = 10000
18 Correct 3 ms 2092 KB Correct answer: answer = 10000
19 Correct 3 ms 2136 KB Correct answer: answer = 624
20 Correct 2 ms 2224 KB Correct answer: answer = 10000
21 Correct 2 ms 2224 KB Correct answer: answer = 1
22 Correct 3 ms 2224 KB Correct answer: answer = 4
23 Correct 2 ms 2224 KB Correct answer: answer = 1
24 Correct 2 ms 2224 KB Correct answer: answer = 5
25 Correct 2 ms 2224 KB Correct answer: answer = 41
26 Incorrect 3 ms 2224 KB Wrong answer: output = 84130, expected = 71923
27 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1908 KB Correct answer: answer = 4
2 Correct 2 ms 1992 KB Correct answer: answer = 4
3 Correct 2 ms 2064 KB Correct answer: answer = 4
4 Correct 2 ms 2064 KB Correct answer: answer = 12
5 Correct 2 ms 2064 KB Correct answer: answer = 52
6 Correct 2 ms 2064 KB Correct answer: answer = 210
7 Correct 2 ms 2068 KB Correct answer: answer = 88
8 Correct 2 ms 2068 KB Correct answer: answer = 7696
9 Correct 2 ms 2068 KB Correct answer: answer = 1
10 Correct 3 ms 2068 KB Correct answer: answer = 2374
11 Correct 2 ms 2068 KB Correct answer: answer = 9502
12 Correct 2 ms 2068 KB Correct answer: answer = 49
13 Correct 2 ms 2084 KB Correct answer: answer = 151
14 Correct 2 ms 2084 KB Correct answer: answer = 7550
15 Correct 2 ms 2084 KB Correct answer: answer = 7220
16 Correct 3 ms 2084 KB Correct answer: answer = 7550
17 Correct 3 ms 2084 KB Correct answer: answer = 10000
18 Correct 3 ms 2092 KB Correct answer: answer = 10000
19 Correct 3 ms 2136 KB Correct answer: answer = 624
20 Correct 2 ms 2224 KB Correct answer: answer = 10000
21 Correct 2 ms 2224 KB Correct answer: answer = 1
22 Correct 3 ms 2224 KB Correct answer: answer = 4
23 Correct 2 ms 2224 KB Correct answer: answer = 1
24 Correct 2 ms 2224 KB Correct answer: answer = 5
25 Correct 2 ms 2224 KB Correct answer: answer = 41
26 Incorrect 3 ms 2224 KB Wrong answer: output = 84130, expected = 71923
27 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1908 KB Correct answer: answer = 4
2 Correct 2 ms 1992 KB Correct answer: answer = 4
3 Correct 2 ms 2064 KB Correct answer: answer = 4
4 Correct 2 ms 2064 KB Correct answer: answer = 12
5 Correct 2 ms 2064 KB Correct answer: answer = 52
6 Correct 2 ms 2064 KB Correct answer: answer = 210
7 Correct 2 ms 2068 KB Correct answer: answer = 88
8 Correct 2 ms 2068 KB Correct answer: answer = 7696
9 Correct 2 ms 2068 KB Correct answer: answer = 1
10 Correct 3 ms 2068 KB Correct answer: answer = 2374
11 Correct 2 ms 2068 KB Correct answer: answer = 9502
12 Correct 2 ms 2068 KB Correct answer: answer = 49
13 Correct 2 ms 2084 KB Correct answer: answer = 151
14 Correct 2 ms 2084 KB Correct answer: answer = 7550
15 Correct 2 ms 2084 KB Correct answer: answer = 7220
16 Correct 3 ms 2084 KB Correct answer: answer = 7550
17 Correct 3 ms 2084 KB Correct answer: answer = 10000
18 Correct 3 ms 2092 KB Correct answer: answer = 10000
19 Correct 3 ms 2136 KB Correct answer: answer = 624
20 Correct 2 ms 2224 KB Correct answer: answer = 10000
21 Correct 2 ms 2224 KB Correct answer: answer = 1
22 Correct 3 ms 2224 KB Correct answer: answer = 4
23 Correct 2 ms 2224 KB Correct answer: answer = 1
24 Correct 2 ms 2224 KB Correct answer: answer = 5
25 Correct 2 ms 2224 KB Correct answer: answer = 41
26 Incorrect 3 ms 2224 KB Wrong answer: output = 84130, expected = 71923
27 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1908 KB Correct answer: answer = 4
2 Correct 2 ms 1992 KB Correct answer: answer = 4
3 Correct 2 ms 2064 KB Correct answer: answer = 4
4 Correct 2 ms 2064 KB Correct answer: answer = 12
5 Correct 2 ms 2064 KB Correct answer: answer = 52
6 Correct 2 ms 2064 KB Correct answer: answer = 210
7 Correct 2 ms 2068 KB Correct answer: answer = 88
8 Correct 2 ms 2068 KB Correct answer: answer = 7696
9 Correct 2 ms 2068 KB Correct answer: answer = 1
10 Correct 3 ms 2068 KB Correct answer: answer = 2374
11 Correct 2 ms 2068 KB Correct answer: answer = 9502
12 Correct 2 ms 2068 KB Correct answer: answer = 49
13 Correct 2 ms 2084 KB Correct answer: answer = 151
14 Correct 2 ms 2084 KB Correct answer: answer = 7550
15 Correct 2 ms 2084 KB Correct answer: answer = 7220
16 Correct 3 ms 2084 KB Correct answer: answer = 7550
17 Correct 3 ms 2084 KB Correct answer: answer = 10000
18 Correct 3 ms 2092 KB Correct answer: answer = 10000
19 Correct 3 ms 2136 KB Correct answer: answer = 624
20 Correct 2 ms 2224 KB Correct answer: answer = 10000
21 Correct 2 ms 2224 KB Correct answer: answer = 1
22 Correct 3 ms 2224 KB Correct answer: answer = 4
23 Correct 2 ms 2224 KB Correct answer: answer = 1
24 Correct 2 ms 2224 KB Correct answer: answer = 5
25 Correct 2 ms 2224 KB Correct answer: answer = 41
26 Incorrect 3 ms 2224 KB Wrong answer: output = 84130, expected = 71923
27 Halted 0 ms 0 KB -