oj.uz

Submission #781211

# Submission time Handle Problem Language Result Execution time Memory
781211 2023-07-12T23:03:20 Z AdamGS Mizuyokan 2 (JOI23_mizuyokan2) C++17
0 / 100
 4000 ms 7960 KB 
    #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-35, 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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 360 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 360 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 360 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 144 ms 1932 KB Output is correct
3 Correct 729 ms 2464 KB Output is correct
4 Execution timed out 4078 ms 2724 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 143 ms 2212 KB Output is correct
4 Correct 726 ms 2524 KB Output is correct
5 Execution timed out 4056 ms 7960 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 360 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -