oj.uz

답안 #477276

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
477276 2021-10-01T14:35:15 Z AkiYuu Building Bridges (CEOI17_building) C++17
60 / 100
 3000 ms 7336 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], s[mxn];
bool sol2;
ll tot = 0;

void subtask1(){

    for (int i = 2; i <= n; i++) {
        dp[i] = LONG_MAX;
        for (int j = 1; j < i; j++)
            dp[i] = min(dp[i],dp[j] + s[i-1] - s[j] + (h[i]-h[j])*(h[i]-h[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];
        s[i] = s[i-1] + 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 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

# 결과 실행 시간 메모리 Grader output
1 Correct 653 ms 5400 KB Output is correct
2 Correct 692 ms 5500 KB Output is correct
3 Correct 653 ms 5504 KB Output is correct
4 Correct 111 ms 2952 KB Output is correct
5 Correct 579 ms 7336 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 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 653 ms 5400 KB Output is correct
7 Correct 692 ms 5500 KB Output is correct
8 Correct 653 ms 5504 KB Output is correct
9 Correct 111 ms 2952 KB Output is correct
10 Correct 579 ms 7336 KB Output is correct
11 Execution timed out 3065 ms 3324 KB Time limit exceeded
12 Halted 0 ms 0 KB -