Submission #455031

#	Time	Username	Problem	Language	Result	Execution time	Memory
455031		MOUF_MAHMALAT	ČVENK (COI15_cvenk)	C++14	22 / 100	27 ms	12364 KiB

cvenk

#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;
}

• Subtask 1: 0 / 17
• Subtask 2: 0 / 21
• Subtask 3: 22 / 22
• Subtask 4: 0 / 40