Submission #118210

#	Time	Username	Problem	Language	Result	Execution time	Memory
118210		imyujin	Lamps (JOI19_lamps)	C++14	100 / 100	86 ms	43512 KiB

lamp

#include<stdio.h>
#include<algorithm>

using namespace std;

#define MAXN 1000005

const int INF=MAXN;
char A[MAXN], B[MAXN];
int dp[MAXN][5], c[MAXN][5];

int main(){
	int N;
	int a[5][5]={{0, 0, 0, 0, 0}, {1, 0, 1, 0, 0}, {1, 1, 0, 0, 0}, {2, 1, 1, 0, 1}, {2, 1, 1, 1, 0}};
	int ans=INF; 

	//freopen("input.txt", "r", stdin);
	scanf("%d\n%s\n%s", &N, A, B);

	for(int i=0; i<N; i++){
		c[i][0]=A[i]==B[i]?0:1;
		c[i][1]=c[i][4]=B[i]=='0'?0:1;
		c[i][2]=c[i][3]=B[i]=='1'?0:1;
	}
	for(int i=0; i<5; i++) dp[0][i]=a[i][0]+c[0][i];
	for(int i=1; i<N; i++) for(int j=0; j<5; j++){
		dp[i][j]=INF;
		for(int k=0; k<5; k++) dp[i][j]=min(dp[i][j], dp[i-1][k]+a[j][k]+(c[i][j]-c[i-1][k]==1?1:0));
	}
	
	for(int i=0; i<5; i++) ans=min(ans, dp[N-1][i]);
	printf("%d", ans);

	return 0;
}

Compilation message (stderr)

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

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