Submission #1102563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102563		YFHHFY	Plus Minus (BOI17_plusminus)	C++14	0 / 100	2 ms	596 KiB

plusminus

#include<bits/stdc++.h>
#define tizoboz ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define ld long double
#define pb push_back
#define int long long
#define itn int
#define ss set <int>
#define prq priority_queue <int>
#define endl '\n'
const ll MOD = 1e9 + 7;
#define md(x) (((x%MOD)+MOD)%MOD)
#define vi vector <int>
#define vl vector<ll>
#define str string 
#define mp make_pair
#define mata int32_t
#define sz size
#define lc id *2
#define rc lc +1
#define SZ(x)           (int)x.size()
#define mid (l+r)/2
#define cn cin
#define ct cout
#define sep " "
#define F first
#define X first
#define S second
#define Y second
using namespace std;
typedef pair <int , int> pii;
const itn maxn = 6;
const int maxm = 2e3 + 10;
const int inf = 1e9;
int n , m , k;
ll dp[maxn][maxn*2];
int g[maxn][maxn];
bool f(int x , int y){
    for (int j = 1 ; j < m ; j++){
        vi w(2 , 0);
        for (int k = j-1 ; k<=j ; k++){
            w[x>>k&1]++;
            w[y>>k&1]++;
        }
        if (!(w[0] == 2 && w[1] == 2)) return false;
    }
    return true;
}
void solve (){
    memset (g , -1 , sizeof g);
    cn >> n >> m >> k;
    while (k--){
        int a , b ;
        char o;
        cn >> o >> a >> b;
        a --;
        b--;
        g[a][b] = (o == '+' ? 1 : 0);
    }
    for (int i = 0 ; i < n ; i ++){
        for (int j = 0 ; j < (1 << m) ; j++){
            bool check = 1;
            for (int k = 0 ; k < m ; k ++){
                if (g[i][k] != -1){
                    if ((j>>k&1) != g[i][k]){
                        check = 0;
                    }
                }
            }
            if (!check)continue;
            if (i == 0){
                dp[i][j] = 1;
            }
            else{
                for (int pma = 0; pma <(1 << m) ; pma++){
                    if (f(pma , j)){
                        dp[i][j] += dp[i-1][pma];
                        dp[i][j] %= MOD;
                    }
                }
            }
        }
    }
    ll res = 0;
    for (int i = 0 ; i < (1 << m) ; i ++){
        res += dp[n-1][i];
        res %= MOD;
    }
    ct << res << endl;
}
mata main(){
    tizoboz;
    int tt = 1;
    // cn >> tt;
    while (tt--){
        solve();
    }
    return 0;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 42
• Subtask 3: 0 / 46