제출 #680293

#제출 시각아이디문제언어결과실행 시간메모리
680293stevancvDischarging (NOI20_discharging)C++14
100 / 100
356 ms88384 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define sp ' ' #define en '\n' #define smin(a, b) a = min(a, b) #define smax(a, b) a = max(a, b) #define sadd(a, b) a = Add(a, b) #define smul(a, b) a = Mul(a, b) using namespace std; const int N = 1e6 + 2; const int mod = 1e9 + 7; ll a[N], dp[N]; struct Line { ll a, b; Line() { a = b = 1e18; } Line(ll aa, ll bb) { a = aa; b = bb; } ll F(int x) { if (a == 1e18 && b == 1e18) return 1e18; return a * x + b; } }st[4 * N]; void Add(int node, int l, int r, Line lin) { int mid = l + r >> 1; bool le = lin.F(l) < st[node].F(l); bool m = lin.F(mid) < st[node].F(mid); if (m) swap(st[node], lin); if (l == r) return; if (le != m) Add(2 * node, l, mid, lin); else Add(2 * node + 1, mid + 1, r, lin); } ll Get(int node, int l, int r, int x) { ll ans = st[node].F(x); if (l == r) return ans; int mid = l + r >> 1; if (x <= mid) smin(ans, Get(2 * node, l, mid, x)); else smin(ans, Get(2 * node + 1, mid + 1, r, x)); return ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; for (int i = 1; i <= 4 * n; i++) st[i] = Line(); for (int i = 1; i <= n; i++) { cin >> a[i]; smax(a[i], a[i - 1]); dp[i] = a[i] * n; } ll ans = 1e18; for (int i = n; i >= 1; i--) { ll o = Get(1, 1, n, i); if (o != 1e18) dp[i] += o; Add(1, 1, n, Line(-a[i], dp[i])); smin(ans, dp[i]); } cout << ans << en; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

Discharging.cpp: In function 'void Add(int, int, int, Line)':
Discharging.cpp:29:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     int mid = l + r >> 1;
      |               ~~^~~
Discharging.cpp: In function 'long long int Get(int, int, int, int)':
Discharging.cpp:40:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     int mid = l + r >> 1;
      |               ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...