oj.uz

답안 #535554

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
535554 2022-03-10T13:34:42 Z MOUF_MAHMALAT Selotejp (COCI20_selotejp) C++14
110 / 110
 166 ms 41180 KB 
#include<bits/stdc++.h>
#define all(s) s.begin(),s.end()
#define F first
#define S second
using namespace std;
typedef int ll;
ll n,m,dp[10][1000][1<<10],o;
bool b[1000][10];
ll best(ll j,ll d,ll mask)
{
    if(j==m)
    {
        j=0;
        d++;
    }
    if(d==n)
        return 0;
    ll &r=dp[j][d][mask];
    if(r!=-1)
        return r;
    if(!b[d][j])
        return r=best(j+1,d,mask&(o^(1<<j)));
    if(j&&((mask&(1<<(j-1)))==0)&&b[d][j-1])
        r=best(j+1,d,mask&(o^(1<<j)));
    else
        r=best(j+1,d,mask&(o^(1<<j)))+1;
    if((mask&(1<<j))!=0)
        r=min(r,best(j+1,d,mask));
    else
        r=min(r,best(j+1,d,mask|(1<<j))+1);
    return r;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(ll i=0; i<n; i++)
        for(ll j=0; j<m; j++)
        {
            char c;
            cin>>c;
            if(c=='#')
                b[i][j]=1;
        }
    o=(1<<m)-1;
    memset(dp,-1,sizeof dp);
    cout<<best(0,0,0);
    return 0;
}

Subtask #1
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 40404 KB Output is correct
2 Correct 21 ms 41140 KB Output is correct
3 Correct 20 ms 40932 KB Output is correct
4 Correct 22 ms 41100 KB Output is correct
5 Correct 22 ms 41172 KB Output is correct
6 Correct 23 ms 41100 KB Output is correct
7 Correct 21 ms 41172 KB Output is correct
8 Correct 19 ms 41068 KB Output is correct
9 Correct 20 ms 41136 KB Output is correct
10 Correct 40 ms 41112 KB Output is correct

Subtask #2
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 40400 KB Output is correct
2 Correct 18 ms 40396 KB Output is correct
3 Correct 17 ms 40376 KB Output is correct
4 Correct 18 ms 40272 KB Output is correct
5 Correct 17 ms 40404 KB Output is correct
6 Correct 17 ms 40324 KB Output is correct
7 Correct 17 ms 40404 KB Output is correct
8 Correct 17 ms 40308 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 40404 KB Output is correct
2 Correct 21 ms 41140 KB Output is correct
3 Correct 20 ms 40932 KB Output is correct
4 Correct 22 ms 41100 KB Output is correct
5 Correct 22 ms 41172 KB Output is correct
6 Correct 23 ms 41100 KB Output is correct
7 Correct 21 ms 41172 KB Output is correct
8 Correct 19 ms 41068 KB Output is correct
9 Correct 20 ms 41136 KB Output is correct
10 Correct 40 ms 41112 KB Output is correct
11 Correct 18 ms 40400 KB Output is correct
12 Correct 18 ms 40396 KB Output is correct
13 Correct 17 ms 40376 KB Output is correct
14 Correct 18 ms 40272 KB Output is correct
15 Correct 17 ms 40404 KB Output is correct
16 Correct 17 ms 40324 KB Output is correct
17 Correct 17 ms 40404 KB Output is correct
18 Correct 17 ms 40308 KB Output is correct
19 Correct 18 ms 40768 KB Output is correct
20 Correct 25 ms 40956 KB Output is correct
21 Correct 25 ms 41052 KB Output is correct
22 Correct 19 ms 41076 KB Output is correct
23 Correct 21 ms 41140 KB Output is correct
24 Correct 20 ms 41172 KB Output is correct
25 Correct 29 ms 41176 KB Output is correct
26 Correct 53 ms 41044 KB Output is correct
27 Correct 97 ms 41180 KB Output is correct
28 Correct 166 ms 41172 KB Output is correct