oj.uz

Submission #1064233

# Submission time Handle Problem Language Result Execution time Memory
1064233 2024-08-18T10:41:57 Z ThylOne Lamps (JOI19_lamps) C++14
0 / 100
 110 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];
    vector<int> st = {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 90 ms 250772 KB Output is correct
2 Correct 94 ms 250844 KB Output is correct
3 Correct 87 ms 250704 KB Output is correct
4 Correct 89 ms 250708 KB Output is correct
5 Correct 88 ms 250896 KB Output is correct
6 Correct 105 ms 250708 KB Output is correct
7 Correct 96 ms 250808 KB Output is correct
8 Correct 89 ms 250900 KB Output is correct
9 Correct 89 ms 250768 KB Output is correct
10 Correct 101 ms 250768 KB Output is correct
11 Correct 103 ms 250736 KB Output is correct
12 Correct 96 ms 250708 KB Output is correct
13 Correct 96 ms 250888 KB Output is correct
14 Correct 92 ms 250912 KB Output is correct
15 Correct 87 ms 250696 KB Output is correct
16 Correct 89 ms 250808 KB Output is correct
17 Correct 96 ms 250808 KB Output is correct
18 Correct 93 ms 250784 KB Output is correct
19 Correct 98 ms 250708 KB Output is correct
20 Correct 90 ms 250708 KB Output is correct
21 Correct 87 ms 250832 KB Output is correct
22 Correct 90 ms 250904 KB Output is correct
23 Correct 87 ms 250772 KB Output is correct
24 Correct 87 ms 250720 KB Output is correct
25 Correct 92 ms 250704 KB Output is correct
26 Incorrect 87 ms 250800 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 250772 KB Output is correct
2 Correct 94 ms 250844 KB Output is correct
3 Correct 87 ms 250704 KB Output is correct
4 Correct 89 ms 250708 KB Output is correct
5 Correct 88 ms 250896 KB Output is correct
6 Correct 105 ms 250708 KB Output is correct
7 Correct 96 ms 250808 KB Output is correct
8 Correct 89 ms 250900 KB Output is correct
9 Correct 89 ms 250768 KB Output is correct
10 Correct 101 ms 250768 KB Output is correct
11 Correct 103 ms 250736 KB Output is correct
12 Correct 96 ms 250708 KB Output is correct
13 Correct 96 ms 250888 KB Output is correct
14 Correct 92 ms 250912 KB Output is correct
15 Correct 87 ms 250696 KB Output is correct
16 Correct 89 ms 250808 KB Output is correct
17 Correct 96 ms 250808 KB Output is correct
18 Correct 93 ms 250784 KB Output is correct
19 Correct 98 ms 250708 KB Output is correct
20 Correct 90 ms 250708 KB Output is correct
21 Correct 87 ms 250832 KB Output is correct
22 Correct 90 ms 250904 KB Output is correct
23 Correct 87 ms 250772 KB Output is correct
24 Correct 87 ms 250720 KB Output is correct
25 Correct 92 ms 250704 KB Output is correct
26 Incorrect 87 ms 250800 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 250784 KB Output is correct
2 Correct 87 ms 250872 KB Output is correct
3 Correct 90 ms 250704 KB Output is correct
4 Correct 110 ms 250708 KB Output is correct
5 Correct 93 ms 250712 KB Output is correct
6 Correct 94 ms 250924 KB Output is correct
7 Runtime error 107 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 90 ms 250772 KB Output is correct
2 Correct 94 ms 250844 KB Output is correct
3 Correct 87 ms 250704 KB Output is correct
4 Correct 89 ms 250708 KB Output is correct
5 Correct 88 ms 250896 KB Output is correct
6 Correct 105 ms 250708 KB Output is correct
7 Correct 96 ms 250808 KB Output is correct
8 Correct 89 ms 250900 KB Output is correct
9 Correct 89 ms 250768 KB Output is correct
10 Correct 101 ms 250768 KB Output is correct
11 Correct 103 ms 250736 KB Output is correct
12 Correct 96 ms 250708 KB Output is correct
13 Correct 96 ms 250888 KB Output is correct
14 Correct 92 ms 250912 KB Output is correct
15 Correct 87 ms 250696 KB Output is correct
16 Correct 89 ms 250808 KB Output is correct
17 Correct 96 ms 250808 KB Output is correct
18 Correct 93 ms 250784 KB Output is correct
19 Correct 98 ms 250708 KB Output is correct
20 Correct 90 ms 250708 KB Output is correct
21 Correct 87 ms 250832 KB Output is correct
22 Correct 90 ms 250904 KB Output is correct
23 Correct 87 ms 250772 KB Output is correct
24 Correct 87 ms 250720 KB Output is correct
25 Correct 92 ms 250704 KB Output is correct
26 Incorrect 87 ms 250800 KB Output isn't correct
27 Halted 0 ms 0 KB -