Submission #781212

#	Time	Username	Problem	Language	Result	Execution time	Memory
781212		AdamGS	Mizuyokan 2 (JOI23_mizuyokan2)	C++17	28 / 100	4070 ms	10200 KiB

mizuyokan2

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define rep(a, b) for(int a = 0; a < (b); ++a)
    #define st first
    #define nd second
    #define pb push_back
    #define all(a) a.begin(), a.end()
    const ll INF=1e9+7;
    const int LIM=25e4+7;
    int dp[LIM];
    ll sum[LIM];
    ll cnt(int l, int r) {
    	return sum[r]-(l?sum[l-1]:0);
    }
    int solve(vector<ll>T) {
    	int n=T.size();
    	rep(i, n) {
    		sum[i]=T[i];
    		if(i) sum[i]+=sum[i-1];
    		dp[i]=-INF;
    	}
    	dp[0]=1;
    	for(int i=1; i<n; ++i) {
    		if(cnt(0, i-1)>T[i]) dp[i]=2;
    		for(int j=i-2; j>=max(i-65, 0); --j) if(cnt(j+1, i-1)>max(T[i], T[j])) dp[i]=max(dp[i], dp[j]+2);
    	}
    	int ans=max(1, dp[n-1]);
    	rep(i, n-1) if(T[i]<cnt(i+1, n-1)) ans=max(ans, dp[i]+1);
    	return ans;
    }
    int main() {
    	ios_base::sync_with_stdio(0); cin.tie(0);
    	int n;
    	cin >> n;
    	vector<ll>T(n);
    	rep(i, n) cin >> T[i];
    	int q;
    	cin >> q;
    	while(q--) {
    		ll x, y, a, b;
    		cin >> x >> y >> a >> b; --x; --b;
    		T[x]=y;
    		vector<ll>P;
    		while(a<=b) {
    			P.pb(T[a]);
    			++a;
    		}
    		cout << solve(P) << '\n';
    	}
    }

• Subtask 1: 6 / 6
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 0 / 32
• Subtask 5: 0 / 29
• Subtask 6: 0 / 11