Submission #132599

#	Time	Username	Problem	Language	Result	Execution time	Memory
132599		ekrem	Lamps (JOI19_lamps)	C++98	100 / 100	292 ms	117884 KiB

lamp

#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)/2)
#define coc g[node][i]
#define mod 1000000007
#define inf 1000000009
#define N 1000005
using namespace std;

typedef long long ll;
typedef pair < int , int > ii;

int n, c[10][10], dp[N][9];
char a[N], b[N];

char yap(char x, int ne){
	char xx = 1 - (x - '0') + '0';
	if(ne == 0 or ne == 3 or ne == 4)
		return '0';
	if(ne == 1 or ne == 2 or ne == 5)
		return '1';
	if(ne == 6)
		return xx;
	return x;
}

int f(int ind, int ne){
	int &r = dp[ind][ne];
	if(r != -1)
		return r;
	if(ind == n + 1)
		return 0;
	r = inf;
	for(int i = 0; i < 8; i++)
		if(yap(a[ind], i) == b[ind]){
			r = min(r, c[ne][i] + f(ind + 1, i));
			// cout << 
		}
	return r;

}

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	memset(dp, -1, sizeof dp);
	scanf("%d %s %s",&n, a + 1, b + 1);
	c[7][7]=0;c[7][0]=1;c[7][1]=1;c[7][2]=2;c[7][3]=2;c[7][4]=2;c[7][5]=3;c[7][6]=1;
	c[6][0]=1;c[6][1]=1;c[6][2]=c[6][3]=c[6][4]=c[6][5]=1;c[6][6]=c[6][7]=0;
	c[5][0]=1;c[5][1]=0;c[5][2]=1;c[5][3]=1;c[5][4]=1;c[5][5]=0;c[5][6]=c[5][7]=0;
	c[4][0]=0;c[4][1]=1;c[4][2]=1;c[4][3]=1;c[4][4]=0;c[4][5]=1;c[4][6]=0;c[4][7]=0;
	c[3][0]=1;c[3][1]=0;c[3][2]=1;c[3][3]=0;c[3][4]=1;c[3][5]=1;c[3][6]=0;c[3][7]=0;
	c[2][0]=0;c[2][1]=1;c[2][2]=0;c[2][3]=1;c[2][4]=1;c[2][5]=1;c[2][6]=0;c[2][7]=0;
	c[1][0]=1;c[1][1]=0;c[1][2]=2;c[1][3]=1;c[1][4]=2;c[1][5]=1;c[1][6]=1;c[1][7]=0;
	c[0][0]=0;c[0][1]=1;c[0][2]=1;c[0][3]=2;c[0][4]=1;c[0][5]=2;c[0][6]=1;c[0][7]=0;
	printf("%d\n", f(1, 7));
	return 0;
}

Compilation message (stderr)

lamp.cpp: In function 'int main()':
lamp.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %s %s",&n, a + 1, b + 1);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 4 / 4
• Subtask 4: 49 / 49