oj.uz

Submission #106616

# Submission time Handle Problem Language Result Execution time Memory
106616 2019-04-19T09:03:49 Z hamzqq9 Lamps (JOI19_lamps) C++14
4 / 100
 50 ms 27768 KB 
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long 
#define ii pair<int,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)/2)
#define all(x) x.begin(),x.end()
#define pw(x) (1<<(x))
#define inf 1000000009
#define MOD 1000000007
#define N 1000006
#define M 2500005
#define LOG 20
#define KOK 300
#define EPS 0.0000001
using namespace std;

int n;
char a[N],b[N];
int dp[N][6];

int main() {

	scanf("%d",&n);

	scanf("%s %s",a+1,b+1);

	for(int i=0;i<=n;i++) {

		for(int j=0;j<6;j++) dp[i][j]=inf;

	}

	dp[0][5]=0;

	for(int i=1;i<=n;i++) {

		if(b[i]=='0') {

			umin(dp[i][0],min(dp[i-1][0],dp[i-1][2]));
			umin(dp[i][0],min(dp[i-1][4],dp[i-1][5])+1);

			umin(dp[i][1],dp[i-1][1]);
			umin(dp[i][1],dp[i-1][3]+1);

		}
		else {

			umin(dp[i][2],dp[i-1][2]);
			umin(dp[i][2],dp[i-1][0]+1);

			umin(dp[i][3],min(dp[i-1][1],dp[i-1][3]));
			umin(dp[i][3],min(dp[i-1][4],dp[i-1][5])+1);

		}

		if(b[i]^a[i]) {

			for(int j=0;j<6;j++) umin(dp[i][4],dp[i-1][j]+(j!=4));

		}
		else {

			for(int j=0;j<6;j++) umin(dp[i][5],dp[i-1][j]);

		}

	}

	int ans=inf;

	for(int i=0;i<6;i++) umin(ans,dp[n][i]);

	printf("%d",ans);

}

Compilation message

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

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 256 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Incorrect 2 ms 256 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 256 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Incorrect 2 ms 256 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 48 ms 27640 KB Output is correct
8 Correct 46 ms 27640 KB Output is correct
9 Correct 41 ms 27640 KB Output is correct
10 Correct 40 ms 27768 KB Output is correct
11 Correct 45 ms 27640 KB Output is correct
12 Correct 50 ms 27640 KB Output is correct
13 Correct 50 ms 27640 KB Output is correct
14 Correct 41 ms 27640 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 256 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Incorrect 2 ms 256 KB Output isn't correct
14 Halted 0 ms 0 KB -