oj.uz

Submission #392625

# Submission time Handle Problem Language Result Execution time Memory
392625 2021-04-21T11:28:01 Z ivan_tudor Aliens (IOI16_aliens) C++14
4 / 100
 1 ms 320 KB 
#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
struct CHT{
  //TODO
  struct Line{
    long long a, b;
    long long id;
    long long operator ()(long long x) const{
      return 1LL * a * x + b;
    }
  };
  deque<Line> dq;
  CHT(){
    dq.clear();
  }
  bool IntersectX(Line l1, Line l2, Line l3){ // daca l2 e scoasa ca minim de l1 si l3
    return (l2.b - l3.b) *(l2.a - l1.a) <= (l1.b - l2.b) *(l3.a - l2.a);
  }
  void AddLine(Line l){
    while(dq.size() > 1 && IntersectX(dq.end()[-2], dq.end()[-1], l))
      dq.pop_back();
    dq.push_back(l);
  }
  pair<long long, int> getmin(long long x){
    while(dq.size() > 1 && dq[0](x) >= dq[1](x))
      dq.pop_front();
    return {dq[0](x), dq[0].id};
  }
};
const long long N = 100005;
struct points{
  long long l, c;
  bool operator <(points oth) const{
    if(l == oth.l)
      return c > oth.c;
    return l < oth.l;
  }
};
points p[N];
long long dp[N], cnt[N];
void makedp(long long n, long long lambda){
  CHT cht;
  for(long long i = 1; i<=n; i++){
    long long extracoef = max(0LL, p[i - 1].c - p[i].l + 1);
    cht.AddLine({-2LL * p[i].l, 1LL * dp[i - 1] + 1LL * p[i].l * p[i].l - extracoef * extracoef, i-1});
    pair<long long, int> dpr = cht.getmin(p[i].c + 1);
    cnt[i] = cnt[dpr.second] + 1;
    dp[i] = dpr.first + lambda + 1LL * (p[i].c + 1) * (p[i].c + 1);
  }
}
long long take_photos(int n, int m, int k, std::vector<int> rows, std::vector<int> columns) {
  for(long long i = 0; i < n; i++){
    long long l = rows[i], c = columns[i];
    l++;
    c++;
    if(l > c)
      swap(l, c);
    p[i+1] = {l, c};
  }
  sort(p + 1, p + n + 1);
  long long maxc = 0;
  vector<points> noup;
  for(long long i = 1; i<=n;){
    long long j = i;
    while(j <=n && p[j].l == p[i].l)
      j++;
    if(p[i].c > maxc){
      noup.push_back(p[i]);
      maxc = p[i].c;
    }
    i = j;
  }
  n = noup.size();
  for(long long i = 1; i<=n; i++)
    p[i] = noup[i - 1];
  long long good = 0;
  for(long long p2 = 1<<50; p2>0; p2/=2){
    makedp(n, good + p2);
    if(cnt[n] >= k)
      good += p2;
  }
  makedp(n, good);
  return dp[n] - k * good;
}

Compilation message

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:78:25: warning: left shift count >= width of type [-Wshift-count-overflow]
   78 |   for(long long p2 = 1<<50; p2>0; p2/=2){
      |                         ^~

Subtask #1
4.0 / 4.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Correct answer: answer = 1
2 Incorrect 1 ms 204 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 1 ms 204 KB Correct answer: answer = 4
2 Correct 1 ms 204 KB Correct answer: answer = 4
3 Correct 0 ms 204 KB Correct answer: answer = 4
4 Correct 1 ms 204 KB Correct answer: answer = 12
5 Correct 1 ms 204 KB Correct answer: answer = 52
6 Correct 0 ms 204 KB Correct answer: answer = 210
7 Correct 1 ms 204 KB Correct answer: answer = 88
8 Correct 1 ms 204 KB Correct answer: answer = 7696
9 Correct 1 ms 320 KB Correct answer: answer = 1
10 Correct 1 ms 204 KB Correct answer: answer = 2374
11 Correct 1 ms 204 KB Correct answer: answer = 9502
12 Correct 1 ms 204 KB Correct answer: answer = 49
13 Correct 1 ms 204 KB Correct answer: answer = 151
14 Correct 1 ms 204 KB Correct answer: answer = 7550
15 Correct 1 ms 204 KB Correct answer: answer = 7220
16 Correct 1 ms 204 KB Correct answer: answer = 7550
17 Correct 1 ms 204 KB Correct answer: answer = 10000
18 Correct 1 ms 204 KB Correct answer: answer = 10000
19 Correct 0 ms 204 KB Correct answer: answer = 624
20 Correct 1 ms 204 KB Correct answer: answer = 10000
21 Correct 1 ms 204 KB Correct answer: answer = 1
22 Incorrect 1 ms 204 KB Wrong answer: output = 2, expected = 4
23 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

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

Subtask #5
0 / 19.0

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

Subtask #6
0 / 40.0

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