oj.uz

답안 #113505

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
113505 2019-05-26T03:23:48 Z raghav0307 Lamps (JOI19_lamps) C++14
4 / 100
 181 ms 112076 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] = 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);
	}
}

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

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 31616 KB Output is correct
2 Correct 24 ms 31608 KB Output is correct
3 Correct 24 ms 31616 KB Output is correct
4 Correct 24 ms 31608 KB Output is correct
5 Correct 25 ms 31616 KB Output is correct
6 Correct 25 ms 31660 KB Output is correct
7 Correct 25 ms 31616 KB Output is correct
8 Correct 25 ms 31588 KB Output is correct
9 Correct 25 ms 31608 KB Output is correct
10 Correct 25 ms 31616 KB Output is correct
11 Correct 25 ms 31608 KB Output is correct
12 Correct 25 ms 31616 KB Output is correct
13 Incorrect 25 ms 31608 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 31616 KB Output is correct
2 Correct 24 ms 31608 KB Output is correct
3 Correct 24 ms 31616 KB Output is correct
4 Correct 24 ms 31608 KB Output is correct
5 Correct 25 ms 31616 KB Output is correct
6 Correct 25 ms 31660 KB Output is correct
7 Correct 25 ms 31616 KB Output is correct
8 Correct 25 ms 31588 KB Output is correct
9 Correct 25 ms 31608 KB Output is correct
10 Correct 25 ms 31616 KB Output is correct
11 Correct 25 ms 31608 KB Output is correct
12 Correct 25 ms 31616 KB Output is correct
13 Incorrect 25 ms 31608 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 31616 KB Output is correct
2 Correct 26 ms 31600 KB Output is correct
3 Correct 25 ms 31616 KB Output is correct
4 Correct 26 ms 31616 KB Output is correct
5 Correct 25 ms 31616 KB Output is correct
6 Correct 26 ms 31608 KB Output is correct
7 Correct 156 ms 112064 KB Output is correct
8 Correct 181 ms 111948 KB Output is correct
9 Correct 162 ms 111984 KB Output is correct
10 Correct 164 ms 112076 KB Output is correct
11 Correct 154 ms 112020 KB Output is correct
12 Correct 153 ms 112072 KB Output is correct
13 Correct 165 ms 112072 KB Output is correct
14 Correct 166 ms 112072 KB Output is correct

Subtask #4
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 31616 KB Output is correct
2 Correct 24 ms 31608 KB Output is correct
3 Correct 24 ms 31616 KB Output is correct
4 Correct 24 ms 31608 KB Output is correct
5 Correct 25 ms 31616 KB Output is correct
6 Correct 25 ms 31660 KB Output is correct
7 Correct 25 ms 31616 KB Output is correct
8 Correct 25 ms 31588 KB Output is correct
9 Correct 25 ms 31608 KB Output is correct
10 Correct 25 ms 31616 KB Output is correct
11 Correct 25 ms 31608 KB Output is correct
12 Correct 25 ms 31616 KB Output is correct
13 Incorrect 25 ms 31608 KB Output isn't correct
14 Halted 0 ms 0 KB -