Submission #822942

#	Time	Username	Problem	Language	Result	Execution time	Memory
822942		vjudge1	Rectangles (IOI19_rect)	C++14	15 / 100	1010 ms	28288 KiB

rect

#include<bits/stdc++.h>
#include "rect.h"
#define fi first
#define se second
#define ll long long
using namespace std ;
ll count_rectangles(vector<vector<int>> v)
{
    ll ans = 0 ;
    int n = v.size(), m = v[0].size() ;
    if(n <= 80 && m <= 80)
    {
        int mx_str[n][m][m] = {}, mx_stl[m][n][n] = {} ;
        for(int i = 0 ; i < n ; i++)
            for(int j = 0 ; j < m ; j++)
            {
                int now = 0 ;
                for(int q = j ; q < m ; q++)
                    now = max(now, v[i][q]), mx_str[i][j][q] = now ;
            }
        for(int i = 0 ; i < m ; i++)
            for(int j = 0 ; j < n ; j++)
            {
                int now = 0 ;
                for(int q = j ; q < n ; q++)
                    now = max(now, v[q][i]), mx_stl[i][j][q] = now ;
            }
        for(int x1 = 1 ; x1 < n - 1 ; x1++)
            for(int y1 = 1 ; y1 < m - 1 ; y1++)
                for(int x2 = x1 ; x2 < n - 1 ; x2++)
                    for(int y2 = y1 ; y2 < m - 1 ; y2++)
                    {
                        bool flag = 1 ;
                        for(int i = x1 ; i <= x2 ; i++)
                            if(mx_str[i][y1][y2] >= min(v[i][y1 - 1], v[i][y2 + 1]))
                                flag &= 0 ;
                        for(int i = y1 ; i <= y2 ; i++)
                            if(mx_stl[i][x1][x2] >= min(v[x1 - 1][i], v[x2 + 1][i]))
                                flag &= 0 ;
                        if(flag)
//                        {
//                            cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << '\n' ;
                            ans += flag ;
//                        }
                    }
    }
    return ans ;
}
//signed main()
//{
//    ios_base::sync_with_stdio( 0 ) ;
//    cin.tie( 0 ) ;
//    cout.tie( 0 ) ;
//    int n, m ;
//    cin >> n >> m ;
//    vector<vector<int>> v ;
//    for(int i = 0 ; i < n ; i++)
//    {
//        vector<int> abu ;
//        for(int j = 0 ; j < m ; j++)
//        {
//            int num ;
//            cin >> num ;
//            abu.push_back(num) ;
//        }
//        v.push_back(abu) ;
//    }
//    cout << count_rectangles(v) ;
//    return 0 ;
//}

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28