oj.uz

Submission #477275

# Submission time Handle Problem Language Result Execution time Memory
477275 2021-10-01T14:27:26 Z AkiYuu Building Bridges (CEOI17_building) C++17
60 / 100
 3000 ms 6532 KB 
#include <bits/stdc++.h>
#define task "GROUP"
#define ll long long
#define ld long double
#define pb(u) emplace_back(u)
#define ffw(i,a,b) for (ll i = a; i <= b; i++)
#define fbw(i,b,a) for (ll i = b; i >= a; i--)
#define adj(v,adj,u) for (auto v : adj[u])
#define rep(i,a) for (auto i : a)
#define reset(a) memset(a, 0, sizeof(a))
#define sz(a) a.size()
#define all(a) a.begin(),a.end()

using namespace std;
const int mxn = 1e6 + 5;
const ll inf = 1e18 + 7;
typedef pair<ll, ll> ii;

void fastio(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
//	freopen(task".inp", "r", stdin);
//	freopen(task".out", "w", stdout);
}

ll n, w[mxn], h[mxn], dp[mxn];
bool sol2;
ll tot = 0;

void subtask1(){
    ll res;
    ffw(i,2,n){
        dp[i] = inf; res = 0;
        fbw(j,i-1,1){
            ll cur = res + dp[j] + (h[i] - h[j]) * (h[i] - h[j]);
            if ( cur < dp[i]) dp[i] = cur;
            res += w[j];
        }
    }
    cout << dp[n] << '\n';
}

ll trans(int i){
    return (h[1]-h[i]) * (h[1]-h[i]) + (h[i]-h[n]) * (h[i]-h[n]) + tot - w[1] - w[i] - w[n];
}

void subtask2(){
    map<ll, set<ll> > check;
    ll res = tot - w[1] - w[n] + (h[n] - h[1]) * (h[n] - h[1]);
    ffw(i,2,n-1){
        ffw(j,-20,20){
            if (check[j].size() != 0){
                auto point = check[j].lower_bound((h[i] + h[1])/2);
                res = min(res, trans(i));
                if ( point != check[j].end())
                    res = min(res,(h[1]-(*point)) * (h[1]-(*point)) + ((*point)-h[i]) * ((*point)-h[i]) +  (h[n]-h[i])*(h[n]-h[i]) + tot - w[1] - w[i] - w[n] - j);
                if ( point != check[j].begin()){
                    --point;
                    res = min(res,(h[1]-(*point)) * (h[1]-(*point)) + ((*point)-h[i]) * ((*point)-h[i]) + (h[n]-h[i]) * (h[n]-h[i]) + tot - w[1] - w[i]- w[n] - j);
                }
            }
        } check[w[i]].insert(h[i]);

    }
    cout << res << '\n';
}

void solve(){
    cin >> n;
    ffw(i,1,n) cin >> h[i];
    sol2 = true;
    ffw(i,1,n) {
        cin >> w[i];
        if ( abs(w[i]) > 20) sol2 = false;
        tot += w[i];
    }
    if (!sol2) subtask1();
    else
        subtask2();
}

int main(){
	fastio();
	solve();
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 619 ms 4556 KB Output is correct
2 Correct 606 ms 4612 KB Output is correct
3 Correct 606 ms 4580 KB Output is correct
4 Correct 110 ms 2160 KB Output is correct
5 Correct 566 ms 6532 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 619 ms 4556 KB Output is correct
7 Correct 606 ms 4612 KB Output is correct
8 Correct 606 ms 4580 KB Output is correct
9 Correct 110 ms 2160 KB Output is correct
10 Correct 566 ms 6532 KB Output is correct
11 Execution timed out 3086 ms 2412 KB Time limit exceeded
12 Halted 0 ms 0 KB -