oj.uz

Submission #477153

# Submission time Handle Problem Language Result Execution time Memory
477153 2021-09-30T23:29:53 Z LptN21 Building Bridges (CEOI17_building) C++14
100 / 100
 122 ms 128588 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=2e18+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 idx=1) {
  if(l==r) {
    if(seg(l) < st[idx](l)) st[idx] = seg;
    return;
  }
  int mid= (l + r)/2, lson = idx*2, rson = idx*2+1;
  if(st[idx].m < seg.m) swap(st[idx], seg);
  if(st[idx](mid) >= seg(mid)) {
    swap(st[idx], seg);
    insert(l, mid, seg, lson);
  } else insert(mid+1, r, seg, rson);
}
ll query(int l, int r, int x, int idx=1) {
  if(l==r) return st[idx](x);
  int mid = (l + r) >> 1, lson = idx*2, rson=idx*2+1;
  if(x <= mid) return min(st[idx](x), query(l, mid, x, lson));
  else return min(st[idx](x), query(mid+1, 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:69:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
building.cpp:70:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     for(int i=1;i<=n;i++) scanf("%d", &a[i]);
      |                           ~~~~~^~~~~~~~~~~~~
building.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         scanf("%d", &m);
      |         ~~~~~^~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 125508 KB Output is correct
2 Correct 54 ms 125468 KB Output is correct
3 Correct 61 ms 125532 KB Output is correct
4 Correct 56 ms 125444 KB Output is correct
5 Correct 57 ms 125508 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 127408 KB Output is correct
2 Correct 107 ms 127476 KB Output is correct
3 Correct 109 ms 127440 KB Output is correct
4 Correct 101 ms 127432 KB Output is correct
5 Correct 98 ms 127424 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 125508 KB Output is correct
2 Correct 54 ms 125468 KB Output is correct
3 Correct 61 ms 125532 KB Output is correct
4 Correct 56 ms 125444 KB Output is correct
5 Correct 57 ms 125508 KB Output is correct
6 Correct 108 ms 127408 KB Output is correct
7 Correct 107 ms 127476 KB Output is correct
8 Correct 109 ms 127440 KB Output is correct
9 Correct 101 ms 127432 KB Output is correct
10 Correct 98 ms 127424 KB Output is correct
11 Correct 118 ms 127480 KB Output is correct
12 Correct 109 ms 127372 KB Output is correct
13 Correct 101 ms 127428 KB Output is correct
14 Correct 122 ms 127376 KB Output is correct
15 Correct 91 ms 127372 KB Output is correct
16 Correct 91 ms 127408 KB Output is correct
17 Correct 87 ms 127428 KB Output is correct
18 Correct 95 ms 128588 KB Output is correct