oj.uz

Submission #113911

# Submission time Handle Problem Language Result Execution time Memory
113911 2019-05-29T07:43:14 Z raghav0307 Lamps (JOI19_lamps) C++14
4 / 100
 203 ms 106320 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][3];

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), MAX_SIZE));
	if(y == 0){
		if(p[x] != q[x]) return memo[x][y] = min(dp(x-1, y) + ( (x == 0 or q[x-1] == p[x-1]) ? 1 : 0), last_min + 1);
		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), MAX_SIZE));
	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 25 ms 23808 KB Output is correct
2 Correct 20 ms 23800 KB Output is correct
3 Correct 22 ms 23800 KB Output is correct
4 Correct 21 ms 23808 KB Output is correct
5 Correct 21 ms 23808 KB Output is correct
6 Correct 21 ms 23808 KB Output is correct
7 Correct 20 ms 23800 KB Output is correct
8 Correct 20 ms 23808 KB Output is correct
9 Correct 20 ms 23776 KB Output is correct
10 Correct 21 ms 23848 KB Output is correct
11 Correct 21 ms 23808 KB Output is correct
12 Correct 21 ms 23808 KB Output is correct
13 Incorrect 20 ms 23808 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23808 KB Output is correct
2 Correct 20 ms 23800 KB Output is correct
3 Correct 22 ms 23800 KB Output is correct
4 Correct 21 ms 23808 KB Output is correct
5 Correct 21 ms 23808 KB Output is correct
6 Correct 21 ms 23808 KB Output is correct
7 Correct 20 ms 23800 KB Output is correct
8 Correct 20 ms 23808 KB Output is correct
9 Correct 20 ms 23776 KB Output is correct
10 Correct 21 ms 23848 KB Output is correct
11 Correct 21 ms 23808 KB Output is correct
12 Correct 21 ms 23808 KB Output is correct
13 Incorrect 20 ms 23808 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 22 ms 23740 KB Output is correct
2 Correct 19 ms 23808 KB Output is correct
3 Correct 19 ms 23808 KB Output is correct
4 Correct 20 ms 23800 KB Output is correct
5 Correct 20 ms 23808 KB Output is correct
6 Correct 21 ms 23808 KB Output is correct
7 Correct 141 ms 106152 KB Output is correct
8 Correct 150 ms 106320 KB Output is correct
9 Correct 143 ms 106176 KB Output is correct
10 Correct 147 ms 106160 KB Output is correct
11 Correct 203 ms 106312 KB Output is correct
12 Correct 148 ms 106148 KB Output is correct
13 Correct 134 ms 106164 KB Output is correct
14 Correct 142 ms 106096 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23808 KB Output is correct
2 Correct 20 ms 23800 KB Output is correct
3 Correct 22 ms 23800 KB Output is correct
4 Correct 21 ms 23808 KB Output is correct
5 Correct 21 ms 23808 KB Output is correct
6 Correct 21 ms 23808 KB Output is correct
7 Correct 20 ms 23800 KB Output is correct
8 Correct 20 ms 23808 KB Output is correct
9 Correct 20 ms 23776 KB Output is correct
10 Correct 21 ms 23848 KB Output is correct
11 Correct 21 ms 23808 KB Output is correct
12 Correct 21 ms 23808 KB Output is correct
13 Incorrect 20 ms 23808 KB Output isn't correct
14 Halted 0 ms 0 KB -