Submission #898886

#	Time	Username	Problem	Language	Result	Execution time	Memory
898886		jamjanek	Garden (JOI23_garden)	C++17	100 / 100	1538 ms	17744 KiB

garden

    #include <bits/stdc++.h>
    using namespace std;
    int wiersz[10010];
    int kolumna[10010];
    bitset<10010> tab[10010];
    int wys[10010];
    int main()
    {
        int n, m, d, i, j, x, y;
        scanf("%d%d%d", &n, &m, &d);
        for(i=0;i<n;i++){
            scanf("%d%d", &x, &y);
            swap(x,y);
            x = d-x-1;
            wiersz[x] = 1;
            kolumna[y] = 1;
            wiersz[x+d] = 1;
            kolumna[y+d] = 1;
        }
        for(i=0;i<m;i++){
            scanf("%d%d", &x, &y);
            swap(x,y);
            x = d-x-1;
            tab[x][y] = 1;
            tab[x+d][y] = 1;
            tab[x][y+d] = 1;
            tab[x+d][y+d] = 1;
        }
        for(i=0;i<2*d;i++)
            if(wiersz[i])
                for(j=0;j<2*d;j++)
                    tab[i][j] = 1;
        for(i=0;i<2*d;i++)
            if(kolumna[i])
                for(j=0;j<2*d;j++)
                    tab[j][i] = 1;
        int wynik = d*d;
        //if(d==4)while(true);
        //for(i=0;i<2*d;i++){for(j=0;j<2*d;j++)printf("%d", (int)tab[i][j]);printf("\n");}
        for(i=0;i<2*d;i++){
            vector<pair<int,int>>KM;
            KM.push_back({-1,-1});
            tab[i][2*d] = 1;
            for(j=0;j<2*d+1;j++){
                if(tab[i][j]==1)
                    wys[j] = 0;
                else
                    wys[j]++;
                while(KM.back().first>=wys[j]){
					if(KM.back().first>0){
//						printf("%d %d: %d %d\n", i, j, KM.back().first, (j-KM[KM.size()-2].second-1));
						wynik = min(wynik, (d-KM.back().first)*(d-(j-KM[KM.size()-2].second-1)));
					}
					KM.pop_back();
				}
//                printf("%d %d: %d %d\n", i, j, wys[j], (j-KM.back().second));
                if(wys[j]>0)
                    wynik = min(wynik,(d-wys[j])*(d-(j-KM.back().second)));
                KM.push_back({wys[j], j});
            }
        }
        j = 0;
        for(i=0;i<2*d;i++){
            if(wiersz[i]==1)
                j = 0;
            else
                j++;
            wynik = min(wynik, d*(d-j));
        }
        j = 0;
        for(i=0;i<2*d;i++){
            if(kolumna[i]==1)
                j = 0;
            else
                j++;
            wynik = min(wynik, d*(d-j));
        }
        printf("%d\n", wynik);
        return 0;
    }
/*
 * 00(14)0
 * 20(0 )0
 * 00(3 )0
 * 00(0 )0
 * 
 * XXXX XXXX
 * X0X0 X0X0
 * 00X0 00X0
 * 00X0 00X0
 * 
 * XXXX XXXX
 * X0X0 X0X0
 * 00X0 00X0
 * 00X0 00X0
*/

Compilation message (stderr)

garden.cpp: In function 'int main()':
garden.cpp:10:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         scanf("%d%d%d", &n, &m, &d);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
garden.cpp:12:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |             scanf("%d%d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~
garden.cpp:21:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |             scanf("%d%d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 6 / 6
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 30 / 30
• Subtask 6: 25 / 25