oj.uz

Submission #1013858

# Submission time Handle Problem Language Result Execution time Memory
1013858 2024-07-04T06:59:02 Z khanhphucscratch Lamps (JOI19_lamps) C++14
4 / 100
 63 ms 33768 KB 
#include<bits/stdc++.h>
using namespace std;
int a[1000005], b[1000005], dp[1000005][6];
int transition(int x, int y)
{
    int ans = 0;
    if(x%2 == 0 && y%2 == 1) ans++;
    if(x/2 != y/2 && y/2 != 2) ans++;
    return ans;
}
int result(int num, int x)
{
    if(x/2 == 0) return 0;
    else if(x/2 == 1) return 1;
    else return (num ^ (x%2));
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i = 1; i <= n; i++){
        char x; cin>>x;
        a[i] = (x == '1');
    }
    for(int i = 1; i <= n; i++){
        char x; cin>>x;
        b[i] = (x == '1');
    }
    for(int i = 0; i <= n; i++) memset(dp[i], 0x3f, sizeof(dp[i]));
    dp[0][4] = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 6; j++) if(dp[i][j] < 1e9){
            for(int k = 0; k < 6; k++){
                if(result(a[i+1], k) == b[i+1]){
                    dp[i+1][k] = min(dp[i+1][k], dp[i][j] + transition(j, k));
                }
            }
        }
    }
    int ans = 1e9;
    for(int i = 0; i < 6; i++) ans = min(ans, dp[n][i]);
    cout<<ans;
}

Subtask #1
0 / 6.0

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

Subtask #2
0 / 41.0

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

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 400 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 59 ms 33700 KB Output is correct
8 Correct 57 ms 33616 KB Output is correct
9 Correct 58 ms 33628 KB Output is correct
10 Correct 63 ms 33624 KB Output is correct
11 Correct 57 ms 33624 KB Output is correct
12 Correct 53 ms 33708 KB Output is correct
13 Correct 63 ms 33768 KB Output is correct
14 Correct 56 ms 33620 KB Output is correct

Subtask #4
0 / 49.0

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