Submission #644518

#	Time	Username	Problem	Language	Result	Execution time	Memory
644518		a_aguilo	Rectangles (IOI19_rect)	C++14	0 / 100	1 ms	596 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>

using namespace std;

vector<vector<int>> Map, dp;

bool possible(int r1, int r2, int c1, int c2){
    long long SumCorn = dp[r2][c2] - dp[r1][c2] - dp[r2][c1] + dp[r1][c1];
    long long int cas = (r2-r1)*(c2-c1);
    if(SumCorn < cas) return false;
    long long other = dp[r2+1][c2+1];
    if(r1 == 0 and c1 == 0){
        other = other;
    }
    else if (r1 == 0){
        other = other - dp[r2+1][c1-1];
    }
    else if(r2 == 0){
        other = other - dp[r1-1][c2+1];
    }
    else{
        other = other - dp[r1-1][c2+1] - dp[r2+1][c1-1] + dp[r1-1][c1-1];
    }
    if(other > SumCorn) return false;
    return true;
}

long long count_rectangles(std::vector<std::vector<int> > a) {
	Map = a;
	dp = vector<vector<int>>(a.size(), vector<int>(a[0].size(), 0));
	dp[0][0] = a[0][0];
	for(int i = 1; i < a.size(); ++i) dp[i][0] = dp[i-1][0] + a[i][0];
	for(int j = 1; j < a[0].size(); ++j) dp[0][j] = dp[0][j-1] + a[0][j];
	for(int i = 1; i < a.size(); ++i){
        for(int j = 1; j < a[0].size(); ++j){
            dp[i][j] = dp[i-1][j] + dp[j][i-1] + a[i][j] - dp[i-1][j-1]; //exclusion-inclusion
        }
	}
	long long ans = 0;
	for(int r1 = 0; r1 < a.size()-1; ++r1){
        for(int r2 = r1+1; r2 < a.size()-1; ++r2){
            for(int c1 = 0; c1 < a[0].size()-1; ++c1){
                for(int c2 = c1+1; c2 < a[0].size()-1; ++c2){
                    if(possible(r1, r2, c1, c2)) ans++;
                }
            }
        }
	}
	return ans;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:33:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for(int i = 1; i < a.size(); ++i) dp[i][0] = dp[i-1][0] + a[i][0];
      |                 ~~^~~~~~~~~~
rect.cpp:34:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for(int j = 1; j < a[0].size(); ++j) dp[0][j] = dp[0][j-1] + a[0][j];
      |                 ~~^~~~~~~~~~~~~
rect.cpp:35:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for(int i = 1; i < a.size(); ++i){
      |                 ~~^~~~~~~~~~
rect.cpp:36:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(int j = 1; j < a[0].size(); ++j){
      |                        ~~^~~~~~~~~~~~~
rect.cpp:41:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for(int r1 = 0; r1 < a.size()-1; ++r1){
      |                  ~~~^~~~~~~~~~~~
rect.cpp:42:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for(int r2 = r1+1; r2 < a.size()-1; ++r2){
      |                            ~~~^~~~~~~~~~~~
rect.cpp:43:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             for(int c1 = 0; c1 < a[0].size()-1; ++c1){
      |                             ~~~^~~~~~~~~~~~~~~
rect.cpp:44:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |                 for(int c2 = c1+1; c2 < a[0].size()-1; ++c2){
      |                                    ~~~^~~~~~~~~~~~~~~

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