oj.uz

답안 #477123

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
477123 2021-09-30T15:52:04 Z LptN21 Building Bridges (CEOI17_building) C++14
60 / 100
 129 ms 128272 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])+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

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 125460 KB Output is correct
2 Correct 59 ms 125424 KB Output is correct
3 Correct 60 ms 125428 KB Output is correct
4 Correct 59 ms 125524 KB Output is correct
5 Correct 67 ms 125488 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 128072 KB Output is correct
2 Correct 107 ms 128028 KB Output is correct
3 Correct 129 ms 128068 KB Output is correct
4 Correct 126 ms 127908 KB Output is correct
5 Correct 96 ms 128000 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 125460 KB Output is correct
2 Correct 59 ms 125424 KB Output is correct
3 Correct 60 ms 125428 KB Output is correct
4 Correct 59 ms 125524 KB Output is correct
5 Correct 67 ms 125488 KB Output is correct
6 Correct 104 ms 128072 KB Output is correct
7 Correct 107 ms 128028 KB Output is correct
8 Correct 129 ms 128068 KB Output is correct
9 Correct 126 ms 127908 KB Output is correct
10 Correct 96 ms 128000 KB Output is correct
11 Correct 115 ms 128272 KB Output is correct
12 Correct 116 ms 128080 KB Output is correct
13 Correct 103 ms 128088 KB Output is correct
14 Correct 115 ms 128224 KB Output is correct
15 Correct 126 ms 127940 KB Output is correct
16 Correct 98 ms 127912 KB Output is correct
17 Incorrect 89 ms 128068 KB Output isn't correct
18 Halted 0 ms 0 KB -