oj.uz

Submission #408963

# Submission time Handle Problem Language Result Execution time Memory
408963 2021-05-19T23:52:03 Z Pichon5 Building Bridges (CEOI17_building) C++17
30 / 100
 72 ms 10156 KB 
#include<bits/stdc++.h>
#define lcm(a,b) (a/__gcd(a,b))*b
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define F first
#define S second
 
//"\n"
//__builtin_popcount
using namespace std;
const int tam=1005;
int n;
ll dp[tam][tam];
vi h,w;
ll f(int pos, int ant){
    if(pos==n-1)return (h[pos]-h[ant])*(h[pos]-h[ant]);
    if(dp[pos][ant]!=-1)return dp[pos][ant];
    dp[pos][ant]=w[pos]+f(pos+1,ant);
    dp[pos][ant]=min(dp[pos][ant],(h[pos]-h[ant])*(h[pos]-h[ant])+f(pos+1,pos));
    return dp[pos][ant];
}
int main()
{
    cin>>n;
    int x;
    for(int i=0;i<n;i++){
        cin>>x;
        h.pb(x);
    }
    for(int i=0;i<n;i++){
        cin>>x;
        w.pb(x);
    }
    memset(dp,-1,sizeof(dp));
    cout<<f(1,0)<<endl;   
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8248 KB Output is correct
2 Correct 4 ms 8140 KB Output is correct
3 Correct 5 ms 8140 KB Output is correct
4 Correct 13 ms 8268 KB Output is correct
5 Correct 14 ms 8268 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 10156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8248 KB Output is correct
2 Correct 4 ms 8140 KB Output is correct
3 Correct 5 ms 8140 KB Output is correct
4 Correct 13 ms 8268 KB Output is correct
5 Correct 14 ms 8268 KB Output is correct
6 Incorrect 72 ms 10156 KB Output isn't correct
7 Halted 0 ms 0 KB -