oj.uz

Submission #1081364

# Submission time Handle Problem Language Result Execution time Memory
1081364 2024-08-30T02:00:33 Z LCJLY Fish 2 (JOI22_fish2) C++14
5 / 100
 333 ms 2484 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<pii,int>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

int arr[505];
int a,b;
int memo[505][505];

bool dp(int l, int r, int val){
	if(l<a&&r>b){
		return true;
	}
	if(memo[l+1][r+1]!=-1) return memo[l+1][r+1];
	//show3(l,l,r,r,val,val);
	//show2(a,a,b,b);
	bool ans=false;
	if(l>=a){
		if(val>=arr[l]){
			ans|=dp(l-1,r,val+arr[l]);
		}
	}
	
	if(r<=b){
		if(val>=arr[r]){
			ans|=dp(l,r+1,val+arr[r]);
		}
	}
	return memo[l+1][r+1]=ans;
}

void solve(){ 	
	int n;
	cin >> n;
	
	for(int x=0;x<n;x++){
		cin >> arr[x];
	}
	
	int q;
	cin >> q;
	int temp,temp2,temp3;
	for(int x=0;x<q;x++){
		cin >> temp >> temp2 >> temp3;
		if(temp==1){
			//add
			temp2--;
			arr[temp2]=temp3;
		}
		else{
			//query
			a=temp2-1;
			b=temp3-1;
			int counter=0;
			memset(memo,-1,sizeof(memo));
			for(int y=a;y<=b;y++){
				counter+=dp(y-1,y+1,arr[y]);
				//show2(y,y,counter,counter);
			}
			cout << counter << "\n";
		}
	}
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	//freopen("in.txt","r",stdin);
	while(t--){
		solve();
	}
}

Compilation message

fish2.cpp: In function 'bool dp(long long int, long long int, long long int)':
fish2.cpp:37:23: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   37 |  return memo[l+1][r+1]=ans;
      |         ~~~~~~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 26 ms 2396 KB Output is correct
6 Correct 80 ms 2468 KB Output is correct
7 Correct 19 ms 2396 KB Output is correct
8 Correct 71 ms 2480 KB Output is correct
9 Correct 122 ms 2392 KB Output is correct
10 Correct 35 ms 2392 KB Output is correct
11 Correct 91 ms 2396 KB Output is correct
12 Correct 25 ms 2392 KB Output is correct
13 Correct 84 ms 2472 KB Output is correct
14 Correct 25 ms 2392 KB Output is correct
15 Correct 48 ms 2484 KB Output is correct
16 Correct 112 ms 2464 KB Output is correct
17 Correct 32 ms 2392 KB Output is correct
18 Correct 99 ms 2468 KB Output is correct
19 Correct 39 ms 2484 KB Output is correct
20 Correct 333 ms 2392 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Runtime error 1 ms 604 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 26 ms 2396 KB Output is correct
6 Correct 80 ms 2468 KB Output is correct
7 Correct 19 ms 2396 KB Output is correct
8 Correct 71 ms 2480 KB Output is correct
9 Correct 122 ms 2392 KB Output is correct
10 Correct 35 ms 2392 KB Output is correct
11 Correct 91 ms 2396 KB Output is correct
12 Correct 25 ms 2392 KB Output is correct
13 Correct 84 ms 2472 KB Output is correct
14 Correct 25 ms 2392 KB Output is correct
15 Correct 48 ms 2484 KB Output is correct
16 Correct 112 ms 2464 KB Output is correct
17 Correct 32 ms 2392 KB Output is correct
18 Correct 99 ms 2468 KB Output is correct
19 Correct 39 ms 2484 KB Output is correct
20 Correct 333 ms 2392 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct
22 Runtime error 1 ms 604 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Runtime error 1 ms 604 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Runtime error 1 ms 604 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 26 ms 2396 KB Output is correct
6 Correct 80 ms 2468 KB Output is correct
7 Correct 19 ms 2396 KB Output is correct
8 Correct 71 ms 2480 KB Output is correct
9 Correct 122 ms 2392 KB Output is correct
10 Correct 35 ms 2392 KB Output is correct
11 Correct 91 ms 2396 KB Output is correct
12 Correct 25 ms 2392 KB Output is correct
13 Correct 84 ms 2472 KB Output is correct
14 Correct 25 ms 2392 KB Output is correct
15 Correct 48 ms 2484 KB Output is correct
16 Correct 112 ms 2464 KB Output is correct
17 Correct 32 ms 2392 KB Output is correct
18 Correct 99 ms 2468 KB Output is correct
19 Correct 39 ms 2484 KB Output is correct
20 Correct 333 ms 2392 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct
22 Runtime error 1 ms 604 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -