Submission #455031

#TimeUsernameProblemLanguageResultExecution timeMemory
455031MOUF_MAHMALATČVENK (COI15_cvenk)C++14
22 / 100
27 ms12364 KiB
#include<bits/stdc++.h>
#define all(s) s.begin(),s.end()
#define F first
#define S second
using namespace std;
typedef long long ll;
ll a[500][500],sz[500][500],ans[500][500],sum=1e18,n;
vector<pair<ll,ll> >v[500][500];
void dfs(ll x,ll y)
{
    //cout<<x<<" "<<y<<endl;
    sz[x][y]+=a[x][y];
    for(auto z:v[x][y])
    {
        dfs(z.F,z.S);
        ans[x][y]+=sz[z.F][z.S]+ans[z.F][z.S];
        sz[x][y]+=sz[z.F][z.S];
    }
}
void best(ll x,ll y,ll sz_up,ll up_sum)
{
    //cout<<x<<" "<<y<<" "<<sz_up<<" "<<up_sum<<endl;
    sum=min(sum,ans[x][y]+up_sum);
    for(auto z:v[x][y])
    {
        ll op=ans[x][y]-ans[z.F][z.S]-sz[z.F][z.S];
        ll sz1=sz_up+sz[x][y]-sz[z.F][z.S];
        best(z.F,z.S,sz1,up_sum+op+sz1);
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    while(n--)
    {
        ll x,y;
        cin>>x>>y;
        a[x][y]++;
    }
    for(ll i=0; i<500; i++)
        for(ll j=0; j<500; j++)
        {
            if(i&j)
                continue;
            if((i+1<500)&&((i+1)&j)==0)
                v[i][j].push_back({i+1,j});
            if((j+1<500)&&((j+1)&i)==0)
                v[i][j].push_back({i,j+1});
        }
    dfs(0,0),best(0,0,0,0);
    cout<<sum;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...