Submission #1297379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297379		suiikami	Cultivation (JOI17_cultivation)	C++20	5 / 100	2 ms	580 KiB

cultivation

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

#define fastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define TIME cerr << "\n--------\nThe program ran in " << 1.0*clock() / CLOCKS_PER_SEC << "s\n";
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Fod(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
//#define int long long
#define all(a) a.begin(),a.end()
#define _ << " " <<
#define _n << "\n"
#define _s << " "
#define endl "\n"
#define fi first
#define se second

const int MOD = 1e9 + 7;
const int oo = INT_MAX;
const ll ooo = LLONG_MAX;
const int simp = 29112008;

int n,r,c;
const int di[4] = {0,-1,0,+1};
const int dj[4] = {-1,0,+1,0};

namespace sub1{
    vector<pair<int,int>> cur;
    int ans = oo;
    bool a[6][6] = {0};
    bool inside(int x,int y){
        if(x < 1 || y < 1) return 0;
        if(x > r || y > c) return 0;
        if(a[x][y]) return 0;
        return 1;
    }
    void Tryy(int cnt){
//            cerr << "count" _ cnt _n;
//            for(auto x : cur) cerr << x.fi _ x.se _n;
//            cerr _n;
        if(cur.size() >= c*r){
            ans = min(ans,cnt);
            return;
        }
        int lim = cur.size();
        for(int i=0;i<4;i++){
            bool can_add = 0;
            for(int j=0; j<lim; j++)
                if(inside(cur[j].fi+di[i],cur[j].se+dj[i])){
                    cur.push_back({cur[j].fi+di[i],cur[j].se+dj[i]});
                    a[cur[j].fi+di[i]][cur[j].se+dj[i]] = 1;
                    can_add = 1;
                }
            if(can_add) Tryy(cnt+1);
            while(cur.size()>lim){
                a[cur.back().fi][cur.back().se] = 0;
                cur.pop_back();
            }
        }
    }
    void process(){
        For(i,1,n){
            int x,y;
            cin >> x >> y;
            cur.push_back({x,y});
            a[x][y] = 1;
        }
        Tryy(0);
        cout << ans _n;
    }
}

#define task "dispersal"
int32_t main(){
    fastIO
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }

    cin >> r >> c >> n;
    if(r <= 4 && c <= 4) sub1::process();

    TIME
    return 0;
}

/*
Code by Melon :d

       /\_____/\
      /   .   . \
     ( ==     == )
      /         \
     / >'imissu' \ >'71646A51706C4E'
    /             \
                __
               / _)
      _.----._/ /
     /         /
  __/ (  | (  |
 /__.-'|_|--|_|

 __CBT 23-26
*/

Compilation message (stderr)

cultivation.cpp: In function 'int32_t main()':
cultivation.cpp:77:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 20
• Subtask 6: 0 / 20