oj.uz

Submission #260385

# Submission time Handle Problem Language Result Execution time Memory
260385 2020-08-10T08:04:53 Z patrikpavic2 Lamps (JOI19_lamps) C++17
4 / 100
 295 ms 229388 KB 
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e6 + 500;

int A[N], B[N], dp[N][2][8], n;

int f(int x, int inv, int msk){
	if(x == n) return 0;
	if(dp[x][inv][msk] != -1) return dp[x][inv][msk];
	int ret = N;
	if(msk & 1) 
		ret = min(ret, f(x, inv, msk - 1));
	if(msk & 2) 
		ret = min(ret, f(x, inv, msk - 2));
	if(msk & 4)
		 ret = min(ret, f(x, inv, msk - 4));
	if(msk == 4)
		ret = min(ret, f(x, inv, 1));
	int zlm = B[x] ^ inv, jos = 0, ol = msk;
	if(A[x] == 0 && zlm == 0){
		if(msk & 4) msk -= 4;
		if((msk & 3) == 1)
			msk = 0;
	}
	if(A[x] == 1 && zlm == 1){
		if((msk & 6) == 2)
			msk -= 2;
	}
	if(A[x] == 1 && zlm == 0){
		if(msk & 4) msk -= 4;
		if(!(msk & 2))
			msk += 2, jos++;
		
	}
	if(A[x] == 0 && zlm == 1){
		if(msk == 3)
			msk = 1;
		if(msk == 2)
			msk += 4, jos++;
		if(msk == 0)
			msk = 1, jos++;
	}
	ret = min(ret, jos + min(f(x + 1, inv, msk), f(x + 1, !inv, msk) + (!inv)));
	return dp[x][inv][ol] = ret;
}

int main(){
	memset(dp, -1, sizeof(dp));
	scanf("%d", &n);
	for(int i = 0;i < n;i++){
		char c; scanf(" %c", &c);
		A[i] = c - '0';
	}
	for(int i = 0;i < n;i++){
		char c; scanf(" %c", &c);
		B[i] = c - '0';
	}
	printf("%d\n", min(f(0, 0, 0), 1 + f(0, 0, 1)));
}

Compilation message

lamp.cpp: In function 'int main()':
lamp.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
lamp.cpp:55:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char c; scanf(" %c", &c);
           ~~~~~^~~~~~~~~~~
lamp.cpp:59:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char c; scanf(" %c", &c);
           ~~~~~^~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 62968 KB Output is correct
2 Correct 33 ms 62968 KB Output is correct
3 Incorrect 33 ms 62924 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 62968 KB Output is correct
2 Correct 33 ms 62968 KB Output is correct
3 Incorrect 33 ms 62924 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 62968 KB Output is correct
2 Correct 28 ms 62944 KB Output is correct
3 Correct 32 ms 62968 KB Output is correct
4 Correct 33 ms 62968 KB Output is correct
5 Correct 33 ms 62968 KB Output is correct
6 Correct 33 ms 62968 KB Output is correct
7 Correct 268 ms 190200 KB Output is correct
8 Correct 295 ms 229244 KB Output is correct
9 Correct 291 ms 229388 KB Output is correct
10 Correct 244 ms 151164 KB Output is correct
11 Correct 248 ms 151036 KB Output is correct
12 Correct 277 ms 190204 KB Output is correct
13 Correct 273 ms 190200 KB Output is correct
14 Correct 272 ms 190072 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 62968 KB Output is correct
2 Correct 33 ms 62968 KB Output is correct
3 Incorrect 33 ms 62924 KB Output isn't correct
4 Halted 0 ms 0 KB -