oj.uz

Submission #113519

# Submission time Handle Problem Language Result Execution time Memory
113519 2019-05-26T05:09:28 Z raghav0307 Lamps (JOI19_lamps) C++14
4 / 100
 198 ms 112840 KB 
/*raghav0307 - Raghav Gupta*/

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

#define ff first
#define ss second
#define pb push_back
#define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

typedef long long ll;
#define int ll
const int MAX_SIZE = 1e6 + 5;
const int inf = 1e15;

int n;
string p, q;

int memo[MAX_SIZE][4];

int dp(int x, int y){
	if(x == -1){
		if(y == 0)	return 0;
		return 1;
	}
	if(memo[x][y] != -1)	return memo[x][y];
	int last_min = min(min(dp(x-1, 0), dp(x-1, 1) ), min(dp(x-1, 2), dp(x-1, 3)));
	if(y == 0){
		if(p[x] != q[x]) return memo[x][y] = inf;
		return memo[x][y] = last_min;
	}
	if(y == 1){
		if(q[x] != '0')	return memo[x][y] = min(dp(x-1, y) + ( (x == 0 or q[x-1] == '0') ? 1 : 0), last_min + 2);
		return memo[x][y]= min(dp(x-1, y), last_min + 1);
	} 
	if(y == 2){
		if(q[x] != '1')	return memo[x][y] = min(dp(x-1, y) + ( (x == 0 or q[x-1] == '1') ? 1 : 0), last_min + 2);
		return memo[x][y] = min(dp(x-1, y), last_min + 1);
	}
	if(y == 3){
		if(q[x] == p[x])	return memo[x][y] = min(dp(x-1, y) + ( x == 0 or q[x-1] != p[x-1] ? 1 : 0), last_min + 2);
		return memo[x][y] = min(dp(x-1, y), last_min + 1);
	}
}

signed main(){
	fast_io();
	cin >> n >> p >> q;
	memset(memo, -1, sizeof(memo));
	int ans = min(min(dp(n-1, 0), dp(n-1, 1)), min(dp(n-1,2), dp(n-1,3)));
	cout << ans << "\n";
	// for(int i = 0; i < n; i++){
	// 	for(int j = 0; j < 4; j++){
	// 		cout << memo[i][j] << " ";
	// 	}cout << "\n";
	// }
	return 0;
}

Compilation message

lamp.cpp: In function 'll dp(ll, ll)':
lamp.cpp:44:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 31608 KB Output is correct
2 Correct 25 ms 31616 KB Output is correct
3 Correct 26 ms 31744 KB Output is correct
4 Correct 26 ms 31616 KB Output is correct
5 Correct 26 ms 31616 KB Output is correct
6 Correct 25 ms 31616 KB Output is correct
7 Correct 25 ms 31616 KB Output is correct
8 Correct 25 ms 31608 KB Output is correct
9 Correct 26 ms 31608 KB Output is correct
10 Correct 25 ms 31608 KB Output is correct
11 Correct 24 ms 31616 KB Output is correct
12 Correct 24 ms 31616 KB Output is correct
13 Incorrect 26 ms 31608 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 31608 KB Output is correct
2 Correct 25 ms 31616 KB Output is correct
3 Correct 26 ms 31744 KB Output is correct
4 Correct 26 ms 31616 KB Output is correct
5 Correct 26 ms 31616 KB Output is correct
6 Correct 25 ms 31616 KB Output is correct
7 Correct 25 ms 31616 KB Output is correct
8 Correct 25 ms 31608 KB Output is correct
9 Correct 26 ms 31608 KB Output is correct
10 Correct 25 ms 31608 KB Output is correct
11 Correct 24 ms 31616 KB Output is correct
12 Correct 24 ms 31616 KB Output is correct
13 Incorrect 26 ms 31608 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 31616 KB Output is correct
2 Correct 24 ms 31616 KB Output is correct
3 Correct 23 ms 31616 KB Output is correct
4 Correct 27 ms 31580 KB Output is correct
5 Correct 24 ms 31616 KB Output is correct
6 Correct 26 ms 31608 KB Output is correct
7 Correct 170 ms 112712 KB Output is correct
8 Correct 162 ms 112840 KB Output is correct
9 Correct 172 ms 112828 KB Output is correct
10 Correct 157 ms 112728 KB Output is correct
11 Correct 158 ms 112836 KB Output is correct
12 Correct 170 ms 112716 KB Output is correct
13 Correct 172 ms 112712 KB Output is correct
14 Correct 198 ms 112716 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 31608 KB Output is correct
2 Correct 25 ms 31616 KB Output is correct
3 Correct 26 ms 31744 KB Output is correct
4 Correct 26 ms 31616 KB Output is correct
5 Correct 26 ms 31616 KB Output is correct
6 Correct 25 ms 31616 KB Output is correct
7 Correct 25 ms 31616 KB Output is correct
8 Correct 25 ms 31608 KB Output is correct
9 Correct 26 ms 31608 KB Output is correct
10 Correct 25 ms 31608 KB Output is correct
11 Correct 24 ms 31616 KB Output is correct
12 Correct 24 ms 31616 KB Output is correct
13 Incorrect 26 ms 31608 KB Output isn't correct
14 Halted 0 ms 0 KB -