oj.uz

Submission #455031

# Submission time Handle Problem Language Result Execution time Memory
455031 2021-08-05T11:45:03 Z MOUF_MAHMALAT ČVENK (COI15_cvenk) C++14
22 / 100
 27 ms 12364 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 12340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 12364 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 12228 KB Output is correct
2 Correct 27 ms 12176 KB Output is correct
3 Correct 25 ms 11768 KB Output is correct
4 Correct 23 ms 11980 KB Output is correct
5 Correct 24 ms 12108 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 12360 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -