Submission #697502

#TimeUsernameProblemLanguageResultExecution timeMemory
697502hct_2so1Discharging (NOI20_discharging)C++14
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> #define MASK(i) (1LL << (i)) #define BIT(x, y) (((x) >> (y)) & 1) #define all(v) (v).begin(), (v).end() #define F first #define S second #define __builtin_popcount __builtin_popcountll #define sz(v) ((int) (v).size()) #define uni(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin()) #define pii(a, b) make_pair(a, b) using namespace std; typedef long long ll; /// const int mod = 1e9 + 7; const int INF = 1e9 + 7; const ll oo = 1e18 + 7; const int N = 1e6 + 5; int n, a[N], nxt[N]; ll dp[N]; struct line { ll a, b; line (const ll &_a = 0, const ll &_b = 0) { a = _a; b = _b; } ll eval(const ll &x) { return a * x + b; } }; deque <line> st; bool bad(const line &l1, const line &l2, const line &l3) { return long double (l3.b - l1.b) * (l1.a - l2.a) < long double (l2.b - l1.b) * (l1.a - l3.a); } void add(const line &x) { while (st.size() >= 2 && bad(st[st.size() - 2], st[st.size() - 1], x)) st.pop_back(); st.push_back(x); } ll query(ll x) { while (st.size() >= 2 && st[0].eval(x) >= st[1].eval(x)) st.pop_front(); return st[0].eval(x); } void Input() { cin >> n; for (int i = 1; i <= n; i ++) cin >> a[i]; nxt[1] = 1; for (int i = 2; i <= n; i ++) if (a[nxt[i - 1]] < a[i]) nxt[i] = i; else nxt[i] = nxt[i - 1]; } void solve() { add(line(0, 0)); for (int i = 1; i <= n; i ++) { dp[i] = query(a[nxt[i]]) + 1LL * n * a[nxt[i]]; add(line(-i, dp[i])); } cout << dp[n]; } int main() { std::ios_base::sync_with_stdio(0); cin.tie(0); // freopen("DIAMOND.inp", "r", stdin); // freopen("DIAMOND.out", "w", stdout); int test = 1; //cin >> test; while (test--) { Input(); solve(); } return 0; }

Compilation message (stderr)

Discharging.cpp: In function 'bool bad(const line&, const line&, const line&)':
Discharging.cpp:45:12: error: expected primary-expression before 'long'
   45 |     return long double (l3.b - l1.b) * (l1.a - l2.a) < long double (l2.b - l1.b) * (l1.a - l3.a);
      |            ^~~~
Discharging.cpp:45:11: error: expected ';' before 'long'
   45 |     return long double (l3.b - l1.b) * (l1.a - l2.a) < long double (l2.b - l1.b) * (l1.a - l3.a);
      |           ^~~~~
      |           ;
Discharging.cpp:45:12: error: expected primary-expression before 'long'
   45 |     return long double (l3.b - l1.b) * (l1.a - l2.a) < long double (l2.b - l1.b) * (l1.a - l3.a);
      |            ^~~~