| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 256338 |
2020-08-02T14:43:39 Z |
lyc |
Lamps (JOI19_lamps) |
C++14 |
|
30 ms |
27860 KB |
#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
#define chmin(x,y) x = min(x,y)
const int mxN = 1e6+5;
int N;
string A, B;
int dp[mxN][6];
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> N >> A >> B;
FOR(x,0,5) dp[N][x] = 0;
RFOR(i,N-1,0){
if (A[i] == B[i]) FOR(x,0,5) dp[i][x] = dp[i+1][0];
else FOR(x,0,5) dp[i][x] = dp[i+1][1] + (x!=1);
if (B[i] == '0') {
chmin(dp[i][0], dp[i+1][2]+1);
chmin(dp[i][1], dp[i+1][2]+1);
chmin(dp[i][2], dp[i+1][2]);
chmin(dp[i][3], dp[i+1][2]);
chmin(dp[i][4], dp[i+1][4]);
chmin(dp[i][5], dp[i+1][4]+1);
} else {
chmin(dp[i][0], dp[i+1][5]+1);
chmin(dp[i][1], dp[i+1][5]+1);
chmin(dp[i][2], dp[i+1][3]+1);
chmin(dp[i][3], dp[i+1][3]);
chmin(dp[i][4], dp[i+1][5]);
chmin(dp[i][5], dp[i+1][5]);
}
//~ cout << i << " :: ";
//~ FOR(x,0,3) cout << dp[i][x] << ' ';
//~ cout << endl;
}
cout << dp[0][0] << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
0 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
0 ms |
384 KB |
Output is correct |
| 11 |
Correct |
0 ms |
384 KB |
Output is correct |
| 12 |
Correct |
0 ms |
384 KB |
Output is correct |
| 13 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
0 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
0 ms |
384 KB |
Output is correct |
| 11 |
Correct |
0 ms |
384 KB |
Output is correct |
| 12 |
Correct |
0 ms |
384 KB |
Output is correct |
| 13 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
0 ms |
384 KB |
Output is correct |
| 7 |
Correct |
28 ms |
27860 KB |
Output is correct |
| 8 |
Correct |
25 ms |
27856 KB |
Output is correct |
| 9 |
Correct |
29 ms |
27852 KB |
Output is correct |
| 10 |
Correct |
25 ms |
27852 KB |
Output is correct |
| 11 |
Correct |
28 ms |
27860 KB |
Output is correct |
| 12 |
Correct |
29 ms |
27852 KB |
Output is correct |
| 13 |
Correct |
25 ms |
27852 KB |
Output is correct |
| 14 |
Correct |
30 ms |
27860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
0 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
0 ms |
384 KB |
Output is correct |
| 11 |
Correct |
0 ms |
384 KB |
Output is correct |
| 12 |
Correct |
0 ms |
384 KB |
Output is correct |
| 13 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
