oj.uz

Submission #582910

# Submission time Handle Problem Language Result Execution time Memory
582910 2022-06-24T15:01:45 Z 600Mihnea Building Bridges (CEOI17_building) C++17
30 / 100
 3000 ms 8184 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long double ld;
typedef long long ll;

const ll INF = (ll) 1e18 + 7;

struct T {
  ll a;
  ll b;
  bool mt = 1;

  ll evaluate(ll x) {
    if (mt) {
      return INF;
    }
    return a * x + b;
  }
};

const int N = (int) 1e5 + 7;
int n;
ll h[N];
ll sum[N];
ll dp[N];
T coef[N];

signed main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  cin >> n;
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    h[i] = x;
  }
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    sum[i] = sum[i - 1] + x;
  }

  dp[1] = 0;
  for (int i = 2; i <= n; i++) {
    dp[i] = INF;
  }

  vector<T> all;

  for (int r = 2; r <= n; r++) {
    T line = {- 2 * h[r - 1], dp[r - 1] + h[r - 1] * h[r - 1] - sum[r - 1]};
    line.mt = 0;

    all.push_back(line);



    ll x = h[r];
    for (auto &ln : all) {
      dp[r] = min(dp[r], ln.a * x + ln.b);
    }
    dp[r] += h[r] * h[r] + sum[r - 1];
  }

  cout << dp[n] << "\n";

}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3060 ms 8184 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Execution timed out 3060 ms 8184 KB Time limit exceeded
7 Halted 0 ms 0 KB -