oj.uz

Submission #599920

# Submission time Handle Problem Language Result Execution time Memory
599920 2022-07-20T09:03:42 Z Shin Building Bridges (CEOI17_building) C++14
30 / 100
 3000 ms 3244 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(), x.end()

using namespace std;
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

const int N = 1e5 + 7;
int n;
int a[N];
long long dp[N];
long long pref[N];

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (int i = 1; i <= n; i ++) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; i ++) {
    int x; cin >> x;
    pref[i] = pref[i - 1] + x;
  }
  #define SQR(x) 1LL * (x) * (x)
  memset(dp, 0x3f, sizeof dp);
  dp[1] = 0;
  for (int i = 2; i <= n; i ++) {
    for (int j = 1; j < i; j ++) {
      minimize(dp[i], dp[j] + SQR(a[i] - a[j]) + pref[i - 1] - pref[j]);
    }
  }
  cout << dp[n];
  return 0;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3074 ms 3244 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 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 3 ms 1108 KB Output is correct
5 Correct 3 ms 1108 KB Output is correct
6 Execution timed out 3074 ms 3244 KB Time limit exceeded
7 Halted 0 ms 0 KB -