oj.uz

Submission #142946

# Submission time Handle Problem Language Result Execution time Memory
142946 2019-08-12T09:11:04 Z Milki Building Bridges (CEOI17_building) C++14
30 / 100
 3000 ms 2868 KB 
#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
#define TRACE(x) cerr << #x << " = " << x << endl

typedef long long ll;
typedef pair<ll, ll> point;

const int MAXN = 1e5 + 5, MAXV = 105;
const ll inf = 1e16;

int n, h[MAXN], w[MAXN];
ll dp[MAXN];

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);

  cin >> n;
  REP(i, n)
    cin >> h[i + 1];
  REP(i, n){
    cin >> w[i + 1];
    if(i > 0)
      w[i + 1] += w[i];
  }

  FOR(i, 2, n + 1){
    dp[i] = inf;
    FOR(j, 1, i)
      dp[i] = min(dp[i], dp[j] + (h[i] - h[j]) * (h[i] - h[j]) + w[i - 1] - w[j] );
  }
  cout << dp[n];
}

Subtask #1
30.0 / 30.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

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