Submission #35818

#	Time	Username	Problem	Language	Result	Execution time	Memory
35818		funcsr	Building Bridges (CEOI17_building)	C++14	30 / 100	3000 ms	10608 KiB

building

#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 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40