oj.uz

Submission #476247

# Submission time Handle Problem Language Result Execution time Memory
476247 2021-09-25T15:24:51 Z LptN21 Building Bridges (CEOI17_building) C++14
60 / 100
 155 ms 127092 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], p[M];
ll _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])-(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
*/

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 55 ms 125504 KB Output is correct
2 Correct 65 ms 125456 KB Output is correct
3 Correct 60 ms 125428 KB Output is correct
4 Correct 51 ms 125508 KB Output is correct
5 Correct 53 ms 125496 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 127012 KB Output is correct
2 Correct 132 ms 127060 KB Output is correct
3 Correct 113 ms 127036 KB Output is correct
4 Correct 95 ms 127052 KB Output is correct
5 Correct 92 ms 126988 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 125504 KB Output is correct
2 Correct 65 ms 125456 KB Output is correct
3 Correct 60 ms 125428 KB Output is correct
4 Correct 51 ms 125508 KB Output is correct
5 Correct 53 ms 125496 KB Output is correct
6 Correct 104 ms 127012 KB Output is correct
7 Correct 132 ms 127060 KB Output is correct
8 Correct 113 ms 127036 KB Output is correct
9 Correct 95 ms 127052 KB Output is correct
10 Correct 92 ms 126988 KB Output is correct
11 Correct 155 ms 127000 KB Output is correct
12 Correct 111 ms 127020 KB Output is correct
13 Correct 99 ms 127064 KB Output is correct
14 Correct 125 ms 127084 KB Output is correct
15 Correct 91 ms 127036 KB Output is correct
16 Correct 91 ms 127016 KB Output is correct
17 Incorrect 94 ms 127092 KB Output isn't correct
18 Halted 0 ms 0 KB -