Submission #1297088

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297088		chaitanyamehta	Lightning Rod (NOI18_lightningrod)	C++20	7 / 100	1106 ms	156136 KiB

Main

#include<bits/stdc++.h>
using namespace std;

#define int long long

signed main(){
    int n;
    cin>>n;
    vector<pair<int , int>> a(n );

    for(int i = 0 ; i < n ;i++)cin>>a[i].first >> a[i].second;

    int total = (1 << n);
    int best = LLONG_MAX;
    for(int i = 0 ; i < total ; i++){
        vector<int> placed(n , 0);
        int ans = 0;
        for(int k = 0 ; k < n; k++){
            if((1 << k) & i){
                placed[k]=1;
                ans++;
                // cout << k << " " << i << " " << ans <<"\n";
            }
        }

        for(int w = 0 ; w < n ; w++){
            if(placed[w]){
                for(int j = w -1; j >= 0; j--){
                
                    if(abs(a[w].first - a[j].first) <= abs(a[w].second - a[j].second))
                    placed[j]=1;
              
                }
                for(int j = w +1; j <n; j++){
                    if(abs(a[w].first - a[j].first) <= abs(a[w].second - a[j].second))
                    placed[j]=1;
                }

            }
        }
        bool ok = true;
        for(int j = 0 ; j< n ; j++){
            if(!placed[j]) ok = false;
        }

        if(ok && ans != 0) best = min(best , ans);
        // if(best == 1){
        //     cout<< i << "\n";
        // }
    }
    cout<<best;
}

• Subtask 1: 0 / 4
• Subtask 2: 7 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 21
• Subtask 5: 0 / 26
• Subtask 6: 0 / 10
• Subtask 7: 0 / 20