oj.uz

Submission #934231

# Submission time Handle Problem Language Result Execution time Memory
934231 2024-02-27T02:58:35 Z UmairAhmadMirza Building Bridges (CEOI17_building) C++14
30 / 100
 3000 ms 3680 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
int const N=1e5+5;
int const inf=1e18+5;
int H[N],W[N],dp[N];
signed main() 
{
  int n;
  cin>>n;
  for(int i=1;i<=n;i++)
    cin>>H[i];
  for(int i=1;i<=n;i++){
    cin>>W[i];
    W[i]+=W[i-1];
  }
  for(int i=2;i<=n;i++){
    dp[i]=inf;
    for(int j=1;j<i;j++){
      int v=abs(H[i]-H[j]);
      v*=v;
      v+=dp[j]+(W[i-1]-W[j]);
      dp[i]=min(dp[i],v);
    }
  }
  cout<<dp[n]<<endl;
  return 0;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
0 / 30.0

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