oj.uz

답안 #497991

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
497991 2021-12-24T08:15:06 Z vinnipuh01 Chessboard (IZhO18_chessboard) C++17
0 / 100
 65 ms 2224 KB 
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <stack>
#include <string>
#include <map>
#include <queue>
#define int long long

using namespace std;

const long long oo = 1000000000000000000;

long long sum, ans = 0, mx = 0, mn = 1000000000, num, pos;


/*
    ViHHiPuh

   (( `'-""``""-'` ))
     )-__-_.._-__-(
   / --- (o _ o) --- \
   \ .-* ( .0. ) *-. /
   _'-. ,_ '=' _, .-'_
  / `;#'#'# - #'#'#;` \
 \_)) -----'#'----- ((_/
      # --------- #
  '# ------- ------ #'
  /..-'# ------- #'-.\
  _\...-\'# -- #'/-.../_
  ((____)- '#' -(____))


    cout << fixed << setprecision(6) << x;

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    freopen ( "sum.in", "r", stdin )
*/

int n, m;
int x[ 100001 ], y[ 100001 ], xx[ 100001 ], yy[ 100001 ];
	
int ff( int x, int y, int r ) {
	int num = 0;
	num = x * y;
	int a, b;
	a = num / 2 + num % 2;
	return a;
}

int f1( int x, int y, int r ) {
	int num = 0, a, b;
	num = x * y;
	b = num / 2;
	return b;
}
	
int f( int x1 ) {
	sum = ( n * n ) / ( x1 * x1 );
	ans = sum / 2;
	num = sum / 2;
	if ( sum % 2 )
		num ++;
	ans = ans * ( x1 * x1 );
	num = num * ( x1 * x1 );
	sum = 0;
	int mx = 0;
	for ( int i = 1; i <= m; i ++ ) {
		sum = ff( xx[ i ], yy[ i ], x1 ) + ff( x[ i ] - 1, y[ i ] - 1, x1 ) - ff( xx[ i ], y[ i ] - 1, x1 ) - ff( x[ i ] - 1, yy[ i ], x1 );
		mx = f1( xx[ i ], yy[ i ], x1 ) + f1( x[ i ] - 1, y[ i ] - 1, x1 ) - f1( xx[ i ], y[ i ] - 1, x1 ) - f1( x[ i ] - 1, yy[ i ], x1 );
		num -= sum;
		num += mx;
		ans -= mx;
		ans += sum;
	}
//	cout << x1 << " " << ans << " " << num << "\n";
	return min( ans, num );
}

main () {
	cin >> n >> m;
	for ( int i = 1; i <= m; i ++ ) {
		cin >> x[ i ] >> y[ i ] >> xx[ i ] >> yy[ i ];
	}
	mn = f( 1 );
	int sqr = sqrt( n * n );
	for ( int i = 2; i <= sqr; i ++ ) {
		if ( ( n * n ) % i == 0 ) {
			mn = min( mn, min( f( i ), f( ( n * n ) / i ) ) );
		}
	}
	cout << mn;
}

/*
6 8
3 3 3 3
1 2 1 2
3 4 3 4
5 5 5 5
4 3 4 3
4 4 4 4
2 1 2 1
3 6 3 6
*/

Compilation message

chessboard.cpp: In function 'long long int ff(long long int, long long int, long long int)':
chessboard.cpp:52:9: warning: unused variable 'b' [-Wunused-variable]
   52 |  int a, b;
      |         ^
chessboard.cpp: In function 'long long int f1(long long int, long long int, long long int)':
chessboard.cpp:58:15: warning: unused variable 'a' [-Wunused-variable]
   58 |  int num = 0, a, b;
      |               ^
chessboard.cpp: At global scope:
chessboard.cpp:86:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   86 | main () {
      | ^~~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 65 ms 2224 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 65 ms 2224 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -