Submission #118210

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
118210	2019-06-18 11:07:30	imyujin	Lamps (JOI19_lamps)	C++14	100 / 100	86 ms	43512 KiB

lamp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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));
  }
  
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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