제출 #292553

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
292553		Autoratch	Rectangles (IOI19_rect)	C++14	37 / 100	5082 ms	88696 KiB

rect

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

const int N = 2501;

int m,n;
int s[N][N],r[N][N],u[N][N],d[N][N],l[N][N],mly[N];
long long ans;

void run(int x,int y)
{
    r[x][y] = y;
    for(int i = 1;;i++)
    {
        if(y+i>n) break;
        if(s[x][y+i]>=s[x][y]) break;
        r[x][y] = y+i;
    }
    l[x][y] = y;
    for(int i = 1;;i++)
    {
        if(y-i<1) break;
        if(s[x][y-i]>=s[x][y]) break;
        l[x][y] = y-i;
    }
    d[x][y] = x;
    for(int i = 1;;i++)
    {
        if(x+i>m) break;
        if(s[x+i][y]>=s[x][y]) break;
        d[x][y] = x+i;
    }
    u[x][y] = x;
    for(int i = 1;;i++)
    {
        if(x-i<1) break;
        if(s[x-i][y]>=s[x][y]) break;
        u[x][y] = x-i;
    }
}

long long count_rectangles(vector<vector<int> > _a)
{
    m = _a.size(),n = _a[0].size();
    for(int i = 0;i < m;i++) for(int j = 0;j < n;j++) s[i+1][j+1] = _a[i][j];
    for(int i = 1;i <= m;i++) for(int j = 1;j <= n;j++) run(i,j);
    for(int i = 1;i <= m;i++) for(int j = i+2;j <= m;j++)
    {
        for(int x = 2;x <= n;x++) 
        {
            int mn = INT_MAX;
            for(int k = i+1;k < j;k++) mn = min(mn,r[k][x-1]);
            for(int y = x;y <= min(mn,n-1);y++)
            {
  //              cout << i << ' ' << j << ' ' << x << ' ' << y << ' ' << d[i][y] << ' ' << u[j][y] << endl;
                if(d[i][y]<j-1 or u[j][y]>i+1) break;
                int mx = INT_MIN;
                for(int k = i+1;k < j;k++) mx = max(mx,l[k][y+1]);
//                cout << i << ' ' << j << ' ' << x << ' ' << y << ' ' << mx << endl;
//                if(mx<=x) cout << i << ' ' << j << ' ' << x << ' ' << y << endl,ans++;
                if(mx<=x) ans++;
            }
        }
    }
    return ans;
}

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