Submission #501858

#	Time	Username	Problem	Language	Result	Execution time	Memory
501858		SirCovidThe19th	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	172 ms	4164 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std; 

#define ll long long

const int md = 1e9 + 7;

struct mint{
	int v;
	mint() : v(0) {}
	mint(ll v_) : v(int(v_ % md)){ if (v < 0) v += md; }
	explicit operator int() const{ return v; }
	friend std::ostream& operator << (std::ostream& out, const mint& n){ return out << int(n); }
	friend std::istream& operator >> (std::istream& in, mint& n){ ll v_; in >> v_; n = mint(v_); return in; }
 
	friend bool operator == (const mint& a, const mint& b){ return a.v == b.v; }
	friend bool operator != (const mint& a, const mint& b){ return a.v != b.v; }
    friend bool operator < (const mint& a, const mint& b){ return a.v < b.v; }
    friend bool operator <= (const mint& a, const mint& b){ return a.v <= b.v; }
    friend bool operator > (const mint& a, const mint& b){ return a.v > b.v; }
	friend bool operator >= (const mint& a, const mint& b){ return a.v >= b.v; }

	mint& operator += (const mint& o){ ((v += o.v) >= md) ? v -= md : 0; return *this; }
	mint& operator -= (const mint& o){ ((v -= o.v) < 0) ? v += md : 0; return *this; }
	mint& operator *= (const mint& o){ v = int((ll)v * o.v % md); return *this; }
	mint& operator /= (const mint& o){ return (*this) *= inv(o); }

	mint operator - () const{ return mint(-v); }
	mint& operator ++ (){ return *this += 1; }
	mint& operator -- (){ return *this -= 1; }
	friend mint operator + (mint a, const mint& b){ return a += b; }
	friend mint operator - (mint a, const mint& b){ return a -= b; }
	friend mint operator * (mint a, const mint& b){ return a *= b; }
	friend mint operator / (mint a, const mint& b){ return a /= b; }

    friend mint pow(mint a, ll p){ return p == 0 ? 1 : pow(a * a, p / 2) * (p & 1 ? a : 1);	}
	friend mint inv(const mint& a){ return pow(a, md - 2); }
};
mint sum(mint x){ return x * (x + 1) / 2; }

int main(){
    int n; cin >> n; 
    mint h[n + 1], w[n + 1], p[n + 1], dp[n + 1], ans; 

    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i <= n; i++) cin >> w[i];
    for (int i = 1; i <= n; i++) p[i] = p[i - 1] + w[i];
    
    stack<int> stk; stk.push(0);

    for (int i = 1; i <= n; i++){
        while (!stk.empty() and h[stk.top()] >= h[i]) stk.pop();
        dp[i] = dp[stk.top()] + sum(h[i]) * (p[i] - p[stk.top()]);
        ans += dp[stk.top()] * w[i] + sum(h[i]) * (p[i - 1] - p[stk.top()]) * w[i] + sum(h[i]) * sum(w[i]);
        stk.push(i);
    }
    cout<<ans<<endl;
}

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 27 / 27