D TLE 3x 求 debug
  • 板块学术版
  • 楼主McIron233
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/3/16 21:47
  • 上次更新2024/3/16 23:47:14
查看原帖
D TLE 3x 求 debug
381463
McIron233楼主2024/3/16 21:47
#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<bits/stdc++.h>
#define pii pair<int,int>
#define int long long
using namespace std;
const int modd=1e9+7;
int n,h,w,vis[15][15];
pii a[15];
bool fnd;
vector<int>vec;
void dfs(int cnt){
    if(fnd)return;
    if(cnt==vec.size()){
        fnd=1; return;
    } for(int i=1;i<=h;++i){
        for(int j=1;j<=w;++j){
            bool flg=1;
            if(i+a[vec[cnt]].first-1>h || j+a[vec[cnt]].second-1>w)continue;
            for(int k=i;k<i+a[vec[cnt]].first;++k){
                for(int l=j;l<j+a[vec[cnt]].second;++l)
                    if(vis[k][l])flg=0;
            } if(flg){
                for(int k=i;k<i+a[vec[cnt]].first;++k){
                    for(int l=j;l<j+a[vec[cnt]].second;++l)
                        vis[k][l]=1;
                } dfs(cnt+1);
                for(int k=i;k<i+a[vec[cnt]].first;++k){
                    for(int l=j;l<j+a[vec[cnt]].second;++l)
                        vis[k][l]=0;
                }
            }
        }
    }
}
bool chk(int s){
    for(int i=1;i<=h;++i){
        for(int j=1;j<=w;++j)vis[i][j]=0;
    } fnd=0; vec.clear(); for(int i=1;i<=n;++i,s>>=1){
        if(s&1)vec.push_back(i);
    } if(vec.empty())return 0;
    dfs(0); return fnd;
}
void Solve(){
    cin>>n>>h>>w;
    for(int i=1;i<=n;++i)cin>>a[i].first>>a[i].second;
    for(int s=0;s<(1<<n);++s){
        int tot=0,t=s; for(int i=1;i<=n;++i,t>>=1){
            if(t&1)tot+=a[i].first*a[i].second;
        } if(tot!=h*w)continue;
        for(int l=0;l<(1<<n);++l){
            t=l; for(int i=1;i<=n;++i,t>>=1){
                if(t&1)swap(a[i].first,a[i].second);
            } if(chk(s)){
                cout<<"Yes"; return;
            } t=l; for(int i=1;i<=n;++i,t>>=1){
                if(t&1)swap(a[i].first,a[i].second);
            }
        }
    } cout<<"No";
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int ___=1;
    while(___--){
        Solve();
    }
    return 0;
}
2024/3/16 21:47
加载中...