Submission #168705

#	Time	Username	Problem	Language	Result	Execution time	Memory
168705		ho94949	Cultivation (JOI17_cultivation)	C++17	5 / 100	863 ms	508 KiB

cultivation

#include<bits/stdc++.h>
using namespace std;
uint64_t B[40];
int main()
{
    int R, C, N;
    scanf("%d%d%d", &R, &C, &N);
    for(int i=0; i<N; ++i)
    {
        int u, v; scanf("%d%d", &u, &v);
        B[u-1] |= (1ull<<(v-1));
    }
    int ans = 202020;
    for(int w=0; w<C; ++w) for(int e=0; e<C; ++e) for(int n=0; n<R; ++n) for(int s=0; s<R; ++s)
    {
        if(w+e>=C || n+s>=R) continue;
        uint64_t A[40]; memcpy(A, B, sizeof A);
        for(int i=0; i<w; ++i)
            for(int j=0; j<R; ++j)
                A[j] |= A[j]>>1;
        for(int i=0; i<e; ++i)
            for(int j=0; j<R; ++j)
                A[j] |= A[j]<<1;
        for(int i=0; i<n; ++i)
            for(int j=0; j<R-1; ++j)
                A[j] |= A[j+1];
        for(int i=0; i<s; ++i)
            for(int j=R-2; j>=0; --j)
                A[j+1] |= A[j];
        uint64_t tar = (1ull<<C)-1;

/*        printf("%d %d %d %d\n", w, e, n, s);
        for(int i=0; i<R; ++i,puts(""))
            for(int j=0; j<C; ++j)
                printf("%d", !!(A[i]&(1<<j)));*/
        for(int i=0; i<R; ++i)
            tar &= A[i];
        
        if(tar == (1ull<<C)-1)
            ans = min(ans, w+e+n+s);
    }
    printf("%d\n", ans);
}

Compilation message (stderr)

cultivation.cpp: In function 'int main()':
cultivation.cpp:7:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &R, &C, &N);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:10:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int u, v; scanf("%d%d", &u, &v);
                   ~~~~~^~~~~~~~~~~~~~~~

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