Hướng dẫn giải của Bedao Mini Contest 17 - PLUS


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: bedao

Nếu biết được vị trí tâm và độ dài của 2 dấu cộng, ta có thể dễ dàng kiểm tra xem 2 dấu cộng đó có giao nhau không trong ~O(1)~. Từ đó, ta có thuật toán ~O(N^6)~ (~15^6~ xấp xỉ ~1e7~ vừa đủ time limit) là duyệt qua cặp tất cả các cặp vị trí là tâm của 2 dấu cộng, sau đó, với mỗi dấu cộng, ta xét tất cả các độ dài có thể của dấu cộng đó và tính tổng bằng Prefix Sum 2D.

Code mẫu

/*
Patrol centre
*/
#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for (ll i=m;i<=n;i++)
#define reb(i,m,n) for (ll i=m;i>=n;i--)
#define rv(i,vt) for (auto i:vt)
#define ii pair<ll,ll>
#define vi vector<ll>
#define F first
#define S second
#define pb push_back
#define sz(v) (int)v.size()
using namespace std;
const ll N=20+5,mod=1e9+7;
vector<ll> bl;
ll n,m,a[N][N],pre[N][N];
ll get (ll x, ll y, ll u, ll v){
    return (pre[u][v]-pre[x-1][v]-pre[u][y-1]+pre[x-1][y-1]);
}
ll cur (ll x, ll y, ll len){
    ll tmp=get(x-len+1,y,x+len-1,y);
    tmp+=get(x,y-len+1,x,y+len-1);
    tmp-=a[x][y];
    return tmp;
}
bool check (ll x, ll y, ll len){
    return (x-len+1>=1 && x+len-1<=n && y-len+1>=1 && y+len-1<=m);
}
bool intersect (ll x1, ll y1, ll len1, ll x2, ll y2, ll len2){
    if (y1==y2) return (abs(x2-x1)<=(len1+len2-2));
    if (x1==x2) return (abs(y2-y1)<=(len1+len2-2));
    if (len1>(abs(x2-x1)) && len2>(abs(y2-y1))) return 1;
    if (len2>(abs(x2-x1)) && len1>abs((y2-y1))) return 1;
    return 0;
}
void elixprep(){

}
void elix()
{
    cin>>n>>m;
    rep(i,1,n)
    rep(j,1,m) cin>>a[i][j],pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+a[i][j];
    ll res=-1e18;
    rep(x,1,n)
    rep(y,1,m)
    rep(u,1,n)
    rep(v,1,m)
    rep(len1,1,20)
    rep(len2,1,20) if (check(x,y,len1) && check(u,v,len2) && !intersect(x,y,len1,u,v,len2)){
    res=max(res,cur(x,y,len1)+cur(u,v,len2));
    }
    cout<<res;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll tests=1;
    //cin>>tests;
    elixprep();
    while (tests--){
        elix();
        cout<<endl;
}
    cerr << "\n" << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
}
//listen to trap music. it won't help

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.