oj.uz

Submission #477154

# Submission time Handle Problem Language Result Execution time Memory
477154 2021-09-30T23:32:56 Z LptN21 Building Bridges (CEOI17_building) C++14
100 / 100
 139 ms 127476 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;
    #define sqr(x) 1LL*(x)*(x)

    insert(1, N, {-2*a[1], sqr(a[1])-p[1]});
    for(int i=2;i<=n;i++) {
        _dp[i]=sqr(a[i])-(p[i]-p[i-1])+query(1, N, a[i]);
        insert(1, N, {-2*a[i], _dp[i]+sqr(a[i])});
        //printf("%d %lld %lld _ %lld\n", i, _dp[i], query(1, N, a[i]), _dp[i]+p[i]);
    }
    printf("%lld", _dp[n]+p[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
*/
/*  AC in real problem: https://oj.uz/problem/view/CEOI17_building
    AC in testlib LibChecker: https://judge.yosupo.jp/problem/line_add_get_min
*/

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 53 ms 125508 KB Output is correct
2 Correct 56 ms 125424 KB Output is correct
3 Correct 59 ms 125512 KB Output is correct
4 Correct 57 ms 125492 KB Output is correct
5 Correct 53 ms 125508 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 127440 KB Output is correct
2 Correct 114 ms 127412 KB Output is correct
3 Correct 107 ms 127428 KB Output is correct
4 Correct 111 ms 127476 KB Output is correct
5 Correct 104 ms 127456 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 125508 KB Output is correct
2 Correct 56 ms 125424 KB Output is correct
3 Correct 59 ms 125512 KB Output is correct
4 Correct 57 ms 125492 KB Output is correct
5 Correct 53 ms 125508 KB Output is correct
6 Correct 109 ms 127440 KB Output is correct
7 Correct 114 ms 127412 KB Output is correct
8 Correct 107 ms 127428 KB Output is correct
9 Correct 111 ms 127476 KB Output is correct
10 Correct 104 ms 127456 KB Output is correct
11 Correct 115 ms 127428 KB Output is correct
12 Correct 139 ms 127408 KB Output is correct
13 Correct 111 ms 127428 KB Output is correct
14 Correct 133 ms 127384 KB Output is correct
15 Correct 95 ms 127396 KB Output is correct
16 Correct 104 ms 127432 KB Output is correct
17 Correct 99 ms 127472 KB Output is correct
18 Correct 100 ms 127376 KB Output is correct