oj.uz

Submission #931533

# Submission time Handle Problem Language Result Execution time Memory
931533 2024-02-22T02:50:09 Z Whisper Selotejp (COCI20_selotejp) C++17
110 / 110
 18 ms 1624 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int long long
#define FOR(i, a, b) for ( int i = a ; i <= b ; i++ )
#define FORD(i, a, b) for (int i = b; i >= a; i --)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPD(i, n) for (int i = n - 1; i >= 0; --i)
#define pii pair<int , int>
#define Lg(x) 31 - __builtin_clz(x)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)

constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int MAX = 1e3 + 5;
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void setupIO(){
    #define name "Whisper"
    //Phu Trong from Nguyen Tat Thanh High School for gifted student
    srand(time(NULL));
    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
    // freopen(name".inp", "r", stdin);
    // freopen(name".out", "w", stdout);
    cout << fixed << setprecision(10);
}

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
int nCol, nRow;
char a[MAX][MAX];
void Whisper(){
    cin >> nRow >> nCol;
    REP(i, nRow) REP(j, nCol) cin >> a[i][j];

    vector<int> F(MASK(nCol)), G(MASK(nCol), INF);
    G[0] = 0;
    REP(i, nRow) REP(j, nCol){
        for (int msk = 0; msk < MASK(nCol); ++msk){
            if (a[i][j] == '.'){
                if (BIT(msk, j)) F[msk] = INF;
                else F[msk] = min(G[msk], G[msk ^ MASK(j)]);
            }
            else{
                if (BIT(msk, j)){
                    F[msk] = min(G[msk], G[msk ^ MASK(j)] + 1);
                }
                else{
                    F[msk] = min(G[msk], G[msk ^ MASK(j)]);
                    if (j == 0 || a[i][j - 1] == '.' || BIT(msk, j - 1)) F[msk]++;
                }
            }
        }
        swap(F, G);
    }
    int ans = INF;
    for (int msk = 0; msk < MASK(nCol); ++msk){
        minimize(ans, G[msk]);
    }
    cout << ans;
    /*
        using dp[i][j][msk] as the minimum that the state i and j is the current row and column
        and the mask that represents what happened on the last m square, the current square, squares
        that are in the current row and on the left side, and square is in the previous row that are
        on the right side of the current square

        bit 0 mean that the row j is covered by a horizontal piece of tape
        bit 1 mean that the row j is covered by a vertical piece of tape

        1. a[i][j] = '.'
            dp[i][j][msk] = min(dp[i][j - 1][msk], dp[i][j - 1][msk ^ MASK(j) + 1]
        2. a[i][j] != '.'
            if (the j - th bit is 1)
                dp[i][j][msk] = min(dp[i][j - 1][msk]) // the previous square has the same state with current
                dp[i][j][msk] = min(dp[i][j - 1][msk ^ MASK(j)] + 1) // (the previous square is covered by a horizontal piece of tape
                so we make a new vertical piece of tap -> + 1)
            if (the j - th bit is 0)
                dp[i][j][msk] = min(dp[i][j][msk, dp[i][j][msk ^ MASK(j)] (update for new state)
                if (i == 0 || s[i][j - 1] == '.' || BIT(msk, j - 1)) dp[i][j][msk]++ (make a new horizontal piece of tape)
        3. we can also optimize the memory by using two array F and G
        F(msk) : the minimum tape we need to cover all the close till i row and j column
        G(msk) : the minimum tape we need to cover all the colose till i row and j - 1 column
    */
}


signed main(){
    setupIO();
    int Test = 1;
//    cin >> Test;
    for ( int i = 1 ; i <= Test ; i++ ){
        Whisper();
        if (i < Test) cout << '\n';
    }
}

Subtask #1
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 15 ms 1372 KB Output is correct
3 Correct 4 ms 1368 KB Output is correct
4 Correct 8 ms 1372 KB Output is correct
5 Correct 16 ms 1372 KB Output is correct
6 Correct 16 ms 1372 KB Output is correct
7 Correct 16 ms 1372 KB Output is correct
8 Correct 15 ms 1368 KB Output is correct
9 Correct 18 ms 1368 KB Output is correct
10 Correct 16 ms 1372 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 15 ms 1372 KB Output is correct
3 Correct 4 ms 1368 KB Output is correct
4 Correct 8 ms 1372 KB Output is correct
5 Correct 16 ms 1372 KB Output is correct
6 Correct 16 ms 1372 KB Output is correct
7 Correct 16 ms 1372 KB Output is correct
8 Correct 15 ms 1368 KB Output is correct
9 Correct 18 ms 1368 KB Output is correct
10 Correct 16 ms 1372 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 1372 KB Output is correct
20 Correct 4 ms 1372 KB Output is correct
21 Correct 8 ms 1372 KB Output is correct
22 Correct 15 ms 1372 KB Output is correct
23 Correct 16 ms 1624 KB Output is correct
24 Correct 16 ms 1372 KB Output is correct
25 Correct 16 ms 1368 KB Output is correct
26 Correct 17 ms 1416 KB Output is correct
27 Correct 17 ms 1372 KB Output is correct
28 Correct 18 ms 1372 KB Output is correct