oj.uz

Submission #823147

# Submission time Handle Problem Language Result Execution time Memory
823147 2023-08-12T08:32:43 Z BidoTeima Lamps (JOI19_lamps) C++17
0 / 100
 1 ms 304 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<int>vec[20];  
int cost[15][15];
int calc(int current, int target){
    if(cost[current][target]!=-1)
        return cost[current][target];
    vector<int>X=vec[current];
    vector<int>Y=vec[target];
        int m = X.size();
    int n = Y.size();
    int L[m + 1][n + 1];
 
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                L[i][j] = 0;
 
            else if (X[i - 1] == Y[j - 1])
                L[i][j] = L[i - 1][j - 1] + 1;
 
            else
                L[i][j] = max(L[i - 1][j], L[i][j - 1]);
        }
    }
    return cost[current][target]=L[m][n];
}
int main()
{        
    memset(cost,-1,sizeof(cost));
    int n;
    string a,b;
    cin>>n>>a>>b;
    for(char&ch:a)ch-='0';
    for(char&ch:b)ch-='0';
    map<vector<int>,int>ind{};
    vector<int>vmsk[20];
    int mask[20];
    int to[2][20];
    int cur=0;
    for(int i = 0; i < 8; i++){
        vector<int>v;
        int msk=0;
        for(int j = 0; j < 3; j++){
            if(i&(1<<j))v.push_back(j),msk+=(1<<j);
        }
        vmsk[msk]=v;
        do{
            vec[cur]=v;
            ind[v]=cur;
            mask[cur]=msk;
            ++cur;
        }while(next_permutation(v.begin(),v.end()));
    }
    int dp[15][n+1];
    for(int i = 0; i < 15; i++){
        for(int j = 0; j < n + 1; j++){
            dp[i][j]=1e6+1;
        }
    }
    for(int i = 0; i < 15; i++){ 
        int val = a[0];
        for(int x : vec[i]){
            if(x==0)val=0;
            else if(x==1)val=1;
            else val ^= 1;
        }
        if(val==b[0]){
            dp[i][0]=vec[i].size();
            //assert(vec[i].size());
        }
        to[a[0]][i]=val;
        val=a[0]^1;
        for(int x : vec[i]){
            if(x==0)val=0;
            else if(x==1)val=1;
            else val ^= 1;
        }
        to[a[0]^1][i]=val;
    }
    /*for(int i = 0; i < n; i++){
        for(int j = 0; j < cur; j++){
            assert(dp[j][i]);
        }
    }*/
    for(int i = 0; i + 1 < n; i++){
        for(int j = 0; j < 15; j++){
            for(int k = 0; k < 15; k++){
                dp[k][i+1]=min(dp[k][i+1],dp[j][i]+calc(j,k));
            }
        }
    }
    int ans = 1e9;
    for(int j = 0; j < 15; j++){
        ans=min(ans,dp[j][n-1]);
    }
    cout<<ans;
    return 0;
}

Compilation message

lamp.cpp: In function 'int main()':
lamp.cpp:73:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   73 |         to[a[0]][i]=val;
      |                ^
lamp.cpp:39:9: warning: variable 'mask' set but not used [-Wunused-but-set-variable]
   39 |     int mask[20];
      |         ^~~~
lamp.cpp:40:9: warning: variable 'to' set but not used [-Wunused-but-set-variable]
   40 |     int to[2][20];
      |         ^~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 304 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -