oj.uz

Submission #113504

# Submission time Handle Problem Language Result Execution time Memory
113504 2019-05-26T03:21:31 Z raghav0307 Lamps (JOI19_lamps) C++14
4 / 100
 142 ms 82764 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;
const int MAX_SIZE = 1e6 + 5;
const int inf = 1e7;

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] = inf;
		return memo[x][y]= min(dp(x-1, y), last_min + 1);
	} 
	if(y == 2){
		if(q[x] != '1')	return memo[x][y] = inf;
		return memo[x][y] = min(dp(x-1, y), last_min + 1);
	}
	if(y == 3){
		if(q[x] == p[x])	return memo[x][y] = inf;
		return memo[x][y] = min(dp(x-1, y), last_min + 1);
	}
}

int 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 'int dp(int, int)':
lamp.cpp:43:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16000 KB Output is correct
2 Correct 15 ms 16000 KB Output is correct
3 Correct 13 ms 16000 KB Output is correct
4 Correct 14 ms 16000 KB Output is correct
5 Correct 13 ms 16000 KB Output is correct
6 Correct 13 ms 16000 KB Output is correct
7 Correct 13 ms 16128 KB Output is correct
8 Correct 14 ms 16000 KB Output is correct
9 Correct 15 ms 16000 KB Output is correct
10 Correct 13 ms 16000 KB Output is correct
11 Correct 13 ms 16000 KB Output is correct
12 Correct 13 ms 16000 KB Output is correct
13 Incorrect 13 ms 16000 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16000 KB Output is correct
2 Correct 15 ms 16000 KB Output is correct
3 Correct 13 ms 16000 KB Output is correct
4 Correct 14 ms 16000 KB Output is correct
5 Correct 13 ms 16000 KB Output is correct
6 Correct 13 ms 16000 KB Output is correct
7 Correct 13 ms 16128 KB Output is correct
8 Correct 14 ms 16000 KB Output is correct
9 Correct 15 ms 16000 KB Output is correct
10 Correct 13 ms 16000 KB Output is correct
11 Correct 13 ms 16000 KB Output is correct
12 Correct 13 ms 16000 KB Output is correct
13 Incorrect 13 ms 16000 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 13 ms 16000 KB Output is correct
2 Correct 14 ms 16000 KB Output is correct
3 Correct 14 ms 16120 KB Output is correct
4 Correct 13 ms 16000 KB Output is correct
5 Correct 13 ms 16000 KB Output is correct
6 Correct 13 ms 16000 KB Output is correct
7 Correct 141 ms 82632 KB Output is correct
8 Correct 132 ms 82764 KB Output is correct
9 Correct 134 ms 82728 KB Output is correct
10 Correct 132 ms 82736 KB Output is correct
11 Correct 142 ms 82632 KB Output is correct
12 Correct 132 ms 82728 KB Output is correct
13 Correct 130 ms 82632 KB Output is correct
14 Correct 133 ms 82664 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16000 KB Output is correct
2 Correct 15 ms 16000 KB Output is correct
3 Correct 13 ms 16000 KB Output is correct
4 Correct 14 ms 16000 KB Output is correct
5 Correct 13 ms 16000 KB Output is correct
6 Correct 13 ms 16000 KB Output is correct
7 Correct 13 ms 16128 KB Output is correct
8 Correct 14 ms 16000 KB Output is correct
9 Correct 15 ms 16000 KB Output is correct
10 Correct 13 ms 16000 KB Output is correct
11 Correct 13 ms 16000 KB Output is correct
12 Correct 13 ms 16000 KB Output is correct
13 Incorrect 13 ms 16000 KB Output isn't correct
14 Halted 0 ms 0 KB -