oj.uz

Submission #224714

# Submission time Handle Problem Language Result Execution time Memory
224714 2020-04-18T16:09:32 Z Bruteforceman Bulldozer (JOI17_bulldozer) C++11
25 / 100
 2000 ms 200216 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair <int, int>;
const int maxn = 2005;
struct point {
  long long x, y, w;
  point () {}
  point (long long x, long long y) : x(x), y(y) {}
  point operator - (point p) {
    return point(x - p.x, y - p.y);
  }
  point operator + (point p) {
    return point(x + p.x, y + p.y);
  }
  point normalize() {
    long long d = __gcd(abs(x), abs(y));
    if(d == 0) return *this;
    else return point(x / d, y / d);
  }
} a[maxn];
long long dot(point p, point q) { return p.x*q.x + p.y*q.y; }
long long cross(point p, point q) { return p.x*q.y - q.x*p.y; }
bool operator < (point p, point q) {
  return cross(p, q) > 0;
}
long long dist(point p) { return dot(p, p); }

bool vis[maxn];
int n;
int cost[maxn];
int pos[maxn], c[maxn];
long long maxSubarray() {
  long long opt = 0;
  long long ans = 0;
  long long sum = 0;
  for(int i = 1; i <= n; i++) {
    sum += cost[i];
    ans = max(ans, sum - opt);
    opt = min(opt, sum);
  }
  return ans;
}

int main() {
  cin >> n;
  long long ans = 0;
  for(int i = 1; i <= n; i++) {
    cin >> a[i].x >> a[i].y >> a[i].w;
    ans = max(ans, a[i].w);
  }
  auto cmp = [&] (point p, point q, point r) {
    return make_pair(cross(p, q), dot(p, q)) < 
      make_pair(cross(p, r), dot(p, r));
  };
  sort(a + 1, a + n + 1, [&] (point p, point q) {
      return cmp(point(1, 0), p, q); });

  map <point, vector <pair <int, int>>> can;
  for(int i = 1; i <= n; i++) {
    for(int j = i + 1; j <= n; j++) {
      point p = a[j] - a[i];
      p = p.normalize();
      can[p].emplace_back(i, j);
    }
  }
  for(int i = 1; i <= n; i++) {
    pos[i] = i;
    c[i] = i;
    cost[i] = a[i].w;
  }
  for(auto i : can) {
    vector <pair <int, int>> v = i.second;
    sort(v.begin(), v.end(), [&] (pii p, pii q) {
      return pos[p.second] - pos[p.first] > pos[q.second] - pos[q.first]; });
    vector <pii> affected;
    for(auto j : v) {
      if(vis[pos[j.first]]) continue;
      for(int k = pos[j.first]; k <= pos[j.second]; k++) {
        vis[k] = true;
      }
      affected.emplace_back(pos[j.first], pos[j.second]);
    }
    ans = max(ans, maxSubarray());
    for(auto j : affected) {
      reverse(c + j.first, c + j.second + 1);
      for(int k = j.first; k <= j.second; k++) {
        vis[k] = false;
        pos[c[k]] = k;
        cost[k] = a[c[k]].w;
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 6 ms 512 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 896 KB Output is correct
2 Correct 8 ms 896 KB Output is correct
3 Correct 8 ms 896 KB Output is correct
4 Correct 8 ms 896 KB Output is correct
5 Correct 9 ms 896 KB Output is correct
6 Correct 9 ms 896 KB Output is correct
7 Correct 8 ms 1024 KB Output is correct
8 Correct 8 ms 1024 KB Output is correct
9 Correct 10 ms 896 KB Output is correct
10 Correct 8 ms 896 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 8 ms 896 KB Output is correct
22 Correct 8 ms 896 KB Output is correct
23 Correct 8 ms 896 KB Output is correct
24 Correct 8 ms 896 KB Output is correct
25 Correct 9 ms 1024 KB Output is correct
26 Correct 8 ms 1024 KB Output is correct
27 Correct 8 ms 896 KB Output is correct
28 Correct 8 ms 896 KB Output is correct
29 Correct 8 ms 896 KB Output is correct
30 Correct 8 ms 896 KB Output is correct
31 Correct 8 ms 896 KB Output is correct
32 Correct 9 ms 1024 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 896 KB Output is correct
2 Correct 8 ms 896 KB Output is correct
3 Correct 8 ms 896 KB Output is correct
4 Correct 8 ms 896 KB Output is correct
5 Correct 9 ms 896 KB Output is correct
6 Correct 9 ms 896 KB Output is correct
7 Correct 8 ms 1024 KB Output is correct
8 Correct 8 ms 1024 KB Output is correct
9 Correct 10 ms 896 KB Output is correct
10 Correct 8 ms 896 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 8 ms 896 KB Output is correct
22 Correct 8 ms 896 KB Output is correct
23 Correct 8 ms 896 KB Output is correct
24 Correct 8 ms 896 KB Output is correct
25 Correct 9 ms 1024 KB Output is correct
26 Correct 8 ms 1024 KB Output is correct
27 Correct 8 ms 896 KB Output is correct
28 Correct 8 ms 896 KB Output is correct
29 Correct 8 ms 896 KB Output is correct
30 Correct 8 ms 896 KB Output is correct
31 Correct 8 ms 896 KB Output is correct
32 Correct 9 ms 1024 KB Output is correct
33 Execution timed out 2102 ms 200216 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 896 KB Output is correct
2 Correct 8 ms 896 KB Output is correct
3 Correct 8 ms 896 KB Output is correct
4 Correct 8 ms 896 KB Output is correct
5 Correct 9 ms 896 KB Output is correct
6 Correct 9 ms 896 KB Output is correct
7 Correct 8 ms 1024 KB Output is correct
8 Correct 8 ms 1024 KB Output is correct
9 Correct 10 ms 896 KB Output is correct
10 Correct 8 ms 896 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 8 ms 896 KB Output is correct
22 Correct 8 ms 896 KB Output is correct
23 Correct 8 ms 896 KB Output is correct
24 Correct 8 ms 896 KB Output is correct
25 Correct 9 ms 1024 KB Output is correct
26 Correct 8 ms 1024 KB Output is correct
27 Correct 8 ms 896 KB Output is correct
28 Correct 8 ms 896 KB Output is correct
29 Correct 8 ms 896 KB Output is correct
30 Correct 8 ms 896 KB Output is correct
31 Correct 8 ms 896 KB Output is correct
32 Correct 9 ms 1024 KB Output is correct
33 Execution timed out 2102 ms 200216 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 6 ms 512 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 9 ms 896 KB Output is correct
17 Correct 8 ms 896 KB Output is correct
18 Correct 8 ms 896 KB Output is correct
19 Correct 8 ms 896 KB Output is correct
20 Correct 9 ms 896 KB Output is correct
21 Correct 9 ms 896 KB Output is correct
22 Correct 8 ms 1024 KB Output is correct
23 Correct 8 ms 1024 KB Output is correct
24 Correct 10 ms 896 KB Output is correct
25 Correct 8 ms 896 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Correct 4 ms 384 KB Output is correct
28 Correct 4 ms 384 KB Output is correct
29 Correct 5 ms 384 KB Output is correct
30 Correct 5 ms 384 KB Output is correct
31 Correct 5 ms 384 KB Output is correct
32 Correct 5 ms 384 KB Output is correct
33 Correct 5 ms 384 KB Output is correct
34 Correct 5 ms 384 KB Output is correct
35 Correct 5 ms 384 KB Output is correct
36 Correct 8 ms 896 KB Output is correct
37 Correct 8 ms 896 KB Output is correct
38 Correct 8 ms 896 KB Output is correct
39 Correct 8 ms 896 KB Output is correct
40 Correct 9 ms 1024 KB Output is correct
41 Correct 8 ms 1024 KB Output is correct
42 Correct 8 ms 896 KB Output is correct
43 Correct 8 ms 896 KB Output is correct
44 Correct 8 ms 896 KB Output is correct
45 Correct 8 ms 896 KB Output is correct
46 Correct 8 ms 896 KB Output is correct
47 Correct 9 ms 1024 KB Output is correct
48 Execution timed out 2102 ms 200216 KB Time limit exceeded
49 Halted 0 ms 0 KB -