Submission #59522457

Source Code Expand

#include<bits/stdc++.h>
#include"atcoder/all"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a) a.begin(),a.end()
typedef long long ll;
typedef vector<ll> vi;
constexpr ll mod = 1000000007;
typedef modint1000000007 mi;

ll x[15],y[15];
ll dist_max[1<<15];
ll dp[16][1<<15];

int main(){
    int n,K;cin>>n>>K;
    rep(i,n)cin>>x[i]>>y[i];

    rep(i,1<<n){
        ll d=0;
        rep(j,n){
            rep(k,j){
                if((i&(1<<j))&&(i&(1<<k)))d=max(d,(x[j]-x[k])*(x[j]-x[k])+(y[j]-y[k])*(y[j]-y[k]));
            }
        }
        dist_max[i]=d;
    }

    rep(i,K+1)rep(j,(1<<n))dp[i][j]=4e18;
    dp[0][0]=0;

    rep(i,K){
        rep(j,1<<n){
            for(int k=j;k<(1<<n);k=(k+1)|j){
                if(j==k)continue;
                dp[i+1][k]=min(dp[i+1][k],max(dp[i][j],dist_max[j^k]));
            }
        }
    }
    cout<<dp[K][(1<<n)-1]<<endl;
}

Submission Info

Submission Time
Task 045 - Simple Grouping（★6）
User Rho17
Language C++ 20 (gcc 12.2)
Score 6
Code Size 968 Byte
Status AC
Exec Time 308 ms
Memory 7320 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 6 / 6
Status
AC × 4
AC × 21
Set Name Test Cases
Sample sample01.txt, sample02.txt, sample03.txt, sample04.txt
All dense00.txt, dense01.txt, dense02.txt, dense03.txt, mid_random00.txt, mid_random01.txt, mid_random02.txt, mid_random03.txt, mid_random04.txt, mid_random05.txt, random00.txt, random01.txt, random02.txt, random03.txt, random04.txt, random05.txt, random06.txt, sample01.txt, sample02.txt, sample03.txt, sample04.txt
Case Name Status Exec Time Memory
dense00.txt AC 2 ms 3532 KiB
dense01.txt AC 2 ms 3520 KiB
dense02.txt AC 1 ms 3552 KiB
dense03.txt AC 54 ms 4452 KiB
mid_random00.txt AC 2 ms 3564 KiB
mid_random01.txt AC 1 ms 3400 KiB
mid_random02.txt AC 1 ms 3512 KiB
mid_random03.txt AC 1 ms 3672 KiB
mid_random04.txt AC 27 ms 4292 KiB
mid_random05.txt AC 2 ms 3496 KiB
random00.txt AC 308 ms 7320 KiB
random01.txt AC 2 ms 3572 KiB
random02.txt AC 8 ms 3824 KiB
random03.txt AC 4 ms 3684 KiB
random04.txt AC 4 ms 3772 KiB
random05.txt AC 1 ms 3484 KiB
random06.txt AC 20 ms 3984 KiB
sample01.txt AC 1 ms 3612 KiB
sample02.txt AC 1 ms 3516 KiB
sample03.txt AC 2 ms 3552 KiB
sample04.txt AC 1 ms 3556 KiB