oj.uz

Submission #35818

# Submission time Handle Problem Language Result Execution time Memory
35818 2017-12-01T02:41:44 Z funcsr Building Bridges (CEOI17_building) C++14
30 / 100
 3000 ms 10608 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(xs) xs.begin(), xs.end()
#define INF (1LL<<60)
using namespace std;

int N;
int H[100000], W[100000];
long long dp[1000001];

signed main() {
  cin >> N;
  rep(i, N) cin >> H[i];
  long long sum = 0;
  rep(i, N) {
    cin >> W[i];
    sum += W[i];
    W[i] = -W[i];
  }
  rep(h, 1000001) dp[h] = INF;
  dp[H[0]] = W[0];
  for (int i=1; i<N-1; i++) {
    long long m = INF;
    rep(h, 1000001) m = min(m, dp[h] + 1LL*(h-H[i])*(h-H[i]));
    dp[H[i]] = min(dp[H[i]], m + W[i]);
  }
  long long m = INF;
  rep(h, 1000001) m = min(m, dp[h] + 1LL*(h-H[N-1])*(h-H[N-1]));
  cout << sum + m + W[N-1] << "\n";
  return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 10608 KB Output is correct
2 Correct 153 ms 10608 KB Output is correct
3 Correct 136 ms 10608 KB Output is correct
4 Correct 1389 ms 10608 KB Output is correct
5 Correct 1329 ms 10608 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3000 ms 10608 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 10608 KB Output is correct
2 Correct 153 ms 10608 KB Output is correct
3 Correct 136 ms 10608 KB Output is correct
4 Correct 1389 ms 10608 KB Output is correct
5 Correct 1329 ms 10608 KB Output is correct
6 Execution timed out 3000 ms 10608 KB Execution timed out
7 Halted 0 ms 0 KB -