oj.uz

Submission #1064236

# Submission time Handle Problem Language Result Execution time Memory
1064236 2024-08-18T10:43:15 Z ThylOne Lamps (JOI19_lamps) C++14
0 / 100
 116 ms 262144 KB 
//####################
//Lamps
//####################
#include<bits/stdc++.h>

using namespace std;
string A,B;
const int inf = 2*1e6;
bool apply(bool a,int m){
    if(m==1)return 0;
    if(m==2)return 1;
    if(m==3)return !a;
    return a;
}
int dp[(int)1e6][4][4][4];
int solve(int pos, int s1=0,int s2=0,int s3=0){
    
    if(pos==A.size())return 0;
    if(dp[pos][s1][s2][s3]!=-1)return dp[pos][s1][s2][s3];
    int re = inf;
    for(int a=0;a<4;a++)
        for(int b=0;b<4;b++)
            for(int c=0;c<4;c++){
                //les cas impossibles
                if(a==0 && (b || c))continue;
                if(b==0 && c)continue;
                if((a==b && a!=0) || (b==c && b!=0) || (a==c && a!=0))continue;
                

                int cost = (bool)a+(bool)b+bool(c);
                if(a==s1){
                    cost-=(bool)a;
                    if(b==s2){
                        cost-=(bool)b;
                        if(c==s3)
                            cost-=(bool)c;
                    }
                }
                
                bool r = (A[pos]-'0');
                r = apply(r,a);
                r = apply(r,b);
                r = apply(r,c);
                if(r==(bool)(B[pos]-'0')){
                    re = min(re, cost+solve(pos+1,a,b,c));
                }
            }
    return dp[pos][s1][s2][s3]=re;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie();
    int n; cin >> n;
    cin >> A >> B;
    for(int i = 0;i<1e6;i++){
         for(int a=0;a<4;a++)
        for(int b=0;b<4;b++)
            for(int c=0;c<4;c++)
                dp[i][a][b][c] = -1;
    }
    cout<<solve(0,0,0,0)<<endl;
    return 0;
};

Compilation message

lamp.cpp: In function 'int solve(int, int, int, int)':
lamp.cpp:18:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     if(pos==A.size())return 0;
      |        ~~~^~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 250704 KB Output is correct
2 Correct 88 ms 250704 KB Output is correct
3 Correct 83 ms 250840 KB Output is correct
4 Correct 92 ms 250708 KB Output is correct
5 Correct 86 ms 250812 KB Output is correct
6 Correct 90 ms 250704 KB Output is correct
7 Correct 87 ms 250708 KB Output is correct
8 Correct 102 ms 250708 KB Output is correct
9 Correct 93 ms 250896 KB Output is correct
10 Correct 90 ms 250708 KB Output is correct
11 Correct 90 ms 250908 KB Output is correct
12 Correct 100 ms 250704 KB Output is correct
13 Correct 89 ms 250708 KB Output is correct
14 Correct 116 ms 250708 KB Output is correct
15 Correct 116 ms 250704 KB Output is correct
16 Correct 103 ms 250912 KB Output is correct
17 Correct 87 ms 250704 KB Output is correct
18 Correct 93 ms 250708 KB Output is correct
19 Correct 93 ms 250708 KB Output is correct
20 Correct 86 ms 250704 KB Output is correct
21 Correct 93 ms 250704 KB Output is correct
22 Correct 96 ms 250708 KB Output is correct
23 Correct 92 ms 250704 KB Output is correct
24 Correct 89 ms 250744 KB Output is correct
25 Correct 93 ms 250708 KB Output is correct
26 Incorrect 85 ms 250704 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 250704 KB Output is correct
2 Correct 88 ms 250704 KB Output is correct
3 Correct 83 ms 250840 KB Output is correct
4 Correct 92 ms 250708 KB Output is correct
5 Correct 86 ms 250812 KB Output is correct
6 Correct 90 ms 250704 KB Output is correct
7 Correct 87 ms 250708 KB Output is correct
8 Correct 102 ms 250708 KB Output is correct
9 Correct 93 ms 250896 KB Output is correct
10 Correct 90 ms 250708 KB Output is correct
11 Correct 90 ms 250908 KB Output is correct
12 Correct 100 ms 250704 KB Output is correct
13 Correct 89 ms 250708 KB Output is correct
14 Correct 116 ms 250708 KB Output is correct
15 Correct 116 ms 250704 KB Output is correct
16 Correct 103 ms 250912 KB Output is correct
17 Correct 87 ms 250704 KB Output is correct
18 Correct 93 ms 250708 KB Output is correct
19 Correct 93 ms 250708 KB Output is correct
20 Correct 86 ms 250704 KB Output is correct
21 Correct 93 ms 250704 KB Output is correct
22 Correct 96 ms 250708 KB Output is correct
23 Correct 92 ms 250704 KB Output is correct
24 Correct 89 ms 250744 KB Output is correct
25 Correct 93 ms 250708 KB Output is correct
26 Incorrect 85 ms 250704 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 250708 KB Output is correct
2 Correct 94 ms 250732 KB Output is correct
3 Correct 85 ms 250704 KB Output is correct
4 Correct 93 ms 250712 KB Output is correct
5 Correct 84 ms 250708 KB Output is correct
6 Correct 86 ms 250708 KB Output is correct
7 Runtime error 104 ms 262144 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 250704 KB Output is correct
2 Correct 88 ms 250704 KB Output is correct
3 Correct 83 ms 250840 KB Output is correct
4 Correct 92 ms 250708 KB Output is correct
5 Correct 86 ms 250812 KB Output is correct
6 Correct 90 ms 250704 KB Output is correct
7 Correct 87 ms 250708 KB Output is correct
8 Correct 102 ms 250708 KB Output is correct
9 Correct 93 ms 250896 KB Output is correct
10 Correct 90 ms 250708 KB Output is correct
11 Correct 90 ms 250908 KB Output is correct
12 Correct 100 ms 250704 KB Output is correct
13 Correct 89 ms 250708 KB Output is correct
14 Correct 116 ms 250708 KB Output is correct
15 Correct 116 ms 250704 KB Output is correct
16 Correct 103 ms 250912 KB Output is correct
17 Correct 87 ms 250704 KB Output is correct
18 Correct 93 ms 250708 KB Output is correct
19 Correct 93 ms 250708 KB Output is correct
20 Correct 86 ms 250704 KB Output is correct
21 Correct 93 ms 250704 KB Output is correct
22 Correct 96 ms 250708 KB Output is correct
23 Correct 92 ms 250704 KB Output is correct
24 Correct 89 ms 250744 KB Output is correct
25 Correct 93 ms 250708 KB Output is correct
26 Incorrect 85 ms 250704 KB Output isn't correct
27 Halted 0 ms 0 KB -