oj.uz

Submission #704993

# Submission time Handle Problem Language Result Execution time Memory
704993 2023-03-03T07:41:34 Z 1075508020060209tc Selotejp (COCI20_selotejp) C++14
70 / 110
 1000 ms 16596 KB 
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define X first
#define Y second
int n;int m;
string tgr[1010];
int dp[1010][3010];
int gr[1010];
int col[3010];
int sme[3010][3010];
int bts[3010];

signed main(){

cin>>n>>m;
for(int i=1;i<=n;i++){
    cin>>tgr[i];
}
for(int i=1;i<=n;i++){
    for(int j=0;j<m;j++){
        if(tgr[i][j]=='#'){
            gr[i]+=(1<<j);
        }
    }
}

for(int i=0;i<(1<<m);i++){
    for(int j=0;j<m;j++){
        if( ((i&(1<<j))!=0) ){
            col[i]++;
            if(j>0&&((i&(1<<(j-1)))!=0)){
                col[i]--;
            }
            bts[i]++;
        }
    }
}
for(int a=0;a<(1<<m);a++){
    for(int b=0;b<(1<<m);b++){
        for(int j=0;j<m;j++){
            if( ((a&(1<<j))!=0)&&((b&(1<<j))!=0) ){
                sme[a][b]++;
            }
        }
    }
}


for(int i=0;i<=n+1;i++){
    for(int j=0;j<(1<<m)+10;j++){
        dp[i][j]=1e9;
    }
}
dp[0][0]=0;

for(int i=1;i<=n+1;i++){
    for(int mask=0;mask<(1<<m);mask++){
        if(((mask|gr[i])!=gr[i])){continue;}
        for(int mskb=0;mskb<(1<<m);mskb++){
            dp[i][mask]=min(dp[i][mask],dp[i-1][mskb]+bts[mask]-sme[mask][mskb]+col[gr[i]^mask]);
        }
    }
}
cout<<dp[n+1][0]<<endl;




}

Subtask #1
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1748 KB Output is correct
2 Correct 41 ms 15916 KB Output is correct
3 Correct 10 ms 6232 KB Output is correct
4 Correct 17 ms 9300 KB Output is correct
5 Correct 50 ms 16560 KB Output is correct
6 Correct 54 ms 16432 KB Output is correct
7 Correct 52 ms 16212 KB Output is correct
8 Correct 31 ms 15948 KB Output is correct
9 Correct 40 ms 15992 KB Output is correct
10 Correct 672 ms 16596 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 8608 KB Output is correct
2 Correct 25 ms 8504 KB Output is correct
3 Correct 23 ms 8536 KB Output is correct
4 Correct 28 ms 8524 KB Output is correct
5 Correct 22 ms 8532 KB Output is correct
6 Correct 23 ms 8532 KB Output is correct
7 Correct 2 ms 1620 KB Output is correct
8 Correct 24 ms 8608 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1748 KB Output is correct
2 Correct 41 ms 15916 KB Output is correct
3 Correct 10 ms 6232 KB Output is correct
4 Correct 17 ms 9300 KB Output is correct
5 Correct 50 ms 16560 KB Output is correct
6 Correct 54 ms 16432 KB Output is correct
7 Correct 52 ms 16212 KB Output is correct
8 Correct 31 ms 15948 KB Output is correct
9 Correct 40 ms 15992 KB Output is correct
10 Correct 672 ms 16596 KB Output is correct
11 Correct 24 ms 8608 KB Output is correct
12 Correct 25 ms 8504 KB Output is correct
13 Correct 23 ms 8536 KB Output is correct
14 Correct 28 ms 8524 KB Output is correct
15 Correct 22 ms 8532 KB Output is correct
16 Correct 23 ms 8532 KB Output is correct
17 Correct 2 ms 1620 KB Output is correct
18 Correct 24 ms 8608 KB Output is correct
19 Correct 2 ms 4436 KB Output is correct
20 Correct 12 ms 6644 KB Output is correct
21 Correct 32 ms 9428 KB Output is correct
22 Correct 28 ms 16316 KB Output is correct
23 Correct 31 ms 16204 KB Output is correct
24 Correct 38 ms 16108 KB Output is correct
25 Correct 96 ms 16328 KB Output is correct
26 Correct 373 ms 16096 KB Output is correct
27 Correct 734 ms 16112 KB Output is correct
28 Execution timed out 1092 ms 16348 KB Time limit exceeded
29 Halted 0 ms 0 KB -