oj.uz

Submission #477124

# Submission time Handle Problem Language Result Execution time Memory
477124 2021-09-30T15:57:56 Z LptN21 Building Bridges (CEOI17_building) C++14
100 / 100
 130 ms 128556 KB 
#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define PI acos(-1.0)
#define FF first
#define SS second
#define eps 1e-9
// vector
#define pb push_back
#define sz(v) int((v).size())
#define all(v) (v).begin(), (v).end()
#define lb lower_bound
#define ub upper_bound
// bit
#define CNTBIT(x) __builtin_popcount(x)
#define ODDBIT(x) __builtin_parity(x)
#define MASK(i) (1ll<<(i))
#define BIT(x, i) (((x)>>(i))&1)
#define SUBSET(big, small) (((big)&(small))==(small))
#define MINBIT(x) (x)&(-x)
// typedef
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef pair<int, ii> i3;
/* CODE BELOW */
const int N=2e6+7, M=1e5+7;
const int MOD=1e9+7;
const ll oo=1e9+9;

int n, m, k, t;

int a[M];
ll p[M], _dp[M];

const ll _oo=1e17+9;

struct Line {
    ll m, b;
    Line() {m=oo;
        b=_oo;
    }
    Line(ll _m, ll _b) {
        m=_m, b=_b;
    }
    ll operator()(ll x) { return m * x + b; }
} st[N<<2];

void insert(int l, int r, Line seg, int o=0) {
  if(l + 1 == r) {
    if(seg(l) < st[o](l)) st[o] = seg;
    return;
  }
  int mid= (l + r) >> 1, lson = o * 2 + 1, rson = o * 2 + 2;
  if(st[o].m < seg.m) swap(st[o], seg);
  if(st[o](mid) > seg(mid)) {
    swap(st[o], seg);
    insert(l, mid, seg, lson);
  } else insert(mid, r, seg, rson);
}
ll query(int l, int r, int x, int o=0) {
  if(l + 1 == r) return st[o](x);
  int mid = (l + r) >> 1, lson = o * 2 + 1, rson = o * 2 + 2;
  if(x < mid) return min(st[o](x), query(l, mid, x, lson));
  else return min(st[o](x), query(mid, r, x, rson));
}

signed main() {
    //freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
    //fastIO;
    scanf("%d", &n);
    for(int i=1;i<=n;i++) scanf("%d", &a[i]);
    for(int i=1;i<=n;i++) {
        scanf("%d", &m);
        p[i]=p[i-1]+m;
    }

    _dp[1]=0;
    const int SUB1=1000;
    #define sqr(x) 1LL*(x)*(x)

    if(n<=SUB1) {
        for(int i=2;i<=n;i++) {
            _dp[i]=oo;
            for(int j=i-1;j>0;j--) {
                ll cost=sqr(a[i]-a[j])+p[i-1]-p[j];
                _dp[i]=min(_dp[i], _dp[j]+cost);
            }
        }
        printf("%lld", _dp[n]);
    } else {
        insert(1, N, {-2*a[1], sqr(a[1])-p[1]});
        for(int i=2;i<=n;i++) {
            _dp[i]=sqr(a[i])+query(1, N, a[i])+p[i-1];
            insert(1, N, {-2*a[i], _dp[i]+sqr(a[i])-p[i]});
            //printf("%d %lld %lld _ %lld\n", i, _dp[i], query(1, N, a[i]), _dp[i]+p[i]);
        }
        printf("%lld", _dp[n]);
    }

    return 0;
}
/* stuff you should look for
    - int overflow, array bounds
    - special/edge cases (n=1?)
    - do smth instead of nothing and stay organized
    - WRITE STUFF DOWN
    - DONT JUST STICK ON ONE APPROACH
*/

Compilation message

building.cpp: In function 'int main()':
building.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
building.cpp:74:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |     for(int i=1;i<=n;i++) scanf("%d", &a[i]);
      |                           ~~~~~^~~~~~~~~~~~~
building.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         scanf("%d", &m);
      |         ~~~~~^~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 125508 KB Output is correct
2 Correct 55 ms 125540 KB Output is correct
3 Correct 56 ms 125500 KB Output is correct
4 Correct 60 ms 125544 KB Output is correct
5 Correct 57 ms 125540 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 127408 KB Output is correct
2 Correct 110 ms 127368 KB Output is correct
3 Correct 101 ms 127428 KB Output is correct
4 Correct 109 ms 127472 KB Output is correct
5 Correct 102 ms 127372 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 125508 KB Output is correct
2 Correct 55 ms 125540 KB Output is correct
3 Correct 56 ms 125500 KB Output is correct
4 Correct 60 ms 125544 KB Output is correct
5 Correct 57 ms 125540 KB Output is correct
6 Correct 111 ms 127408 KB Output is correct
7 Correct 110 ms 127368 KB Output is correct
8 Correct 101 ms 127428 KB Output is correct
9 Correct 109 ms 127472 KB Output is correct
10 Correct 102 ms 127372 KB Output is correct
11 Correct 130 ms 127468 KB Output is correct
12 Correct 125 ms 127376 KB Output is correct
13 Correct 107 ms 127472 KB Output is correct
14 Correct 119 ms 127416 KB Output is correct
15 Correct 98 ms 127428 KB Output is correct
16 Correct 104 ms 127428 KB Output is correct
17 Correct 107 ms 127452 KB Output is correct
18 Correct 102 ms 128556 KB Output is correct