codeforces C#264. Gargari and Bishops

2024-06-05 21:32

本文主要是介绍codeforces C#264. Gargari and Bishops,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Gargari is jealous that his friend Caisa won the game from the previous problem. He wants to prove that he is a genius.

He has a n × n chessboard. Each cell of the chessboard has a number written on it. Gargari wants to place two bishops on the chessboard in such a way that there is no cell that is attacked by both of them. Consider a cell with number x written on it, if this cell is attacked by one of the bishops Gargari will getx dollars for it. Tell Gargari, how to place bishops on the chessboard to get maximum amount of money.

We assume a cell is attacked by a bishop, if the cell is located on the same diagonal with the bishop (the cell, where the bishop is, also considered attacked by it).

Input

The first line contains a single integer n(2 ≤ n ≤ 2000). Each of the next n lines contains n integersaij(0 ≤ aij ≤ 109) — description of the chessboard.

Output

On the first line print the maximal number of dollars Gargari will get. On the next line print four integers:x1, y1, x2, y2(1 ≤ x1, y1, x2, y2 ≤ n), wherexi is the number of the row where thei-th bishop should be placed, yi is the number of the column where thei-th bishop should be placed. Consider rows are numbered from 1 ton from top to bottom, and columns are numbered from 1 ton from left to right.

If there are several optimal solutions, you can print any of them.

Sample test(s)
Input
4
1 1 1 1
2 1 1 0
1 1 1 0
1 0 0 1
Output
12
2 2 3 2
题意:给你个n*n的矩阵,对于一个点我们可以统计经过它的斜线上的值,让你选两个点,且经过的斜线是不相交的,求这两个点能组成的最大权值
思路:首先预处理出主负斜线上的值,然后就是把矩阵划分成类似国际象棋的黑白格子,分别计算黑白格子的最大值
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long ll;
using namespace std;
const int maxn = 2005;ll arr[maxn*2];
ll brr[maxn*2];
int num[maxn][maxn];int main() {int n, a;scanf("%d", &n);memset(arr, 0, sizeof(arr));memset(brr, 0, sizeof(brr));for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) {scanf("%d", &num[i][j]);}for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++) {arr[i-j+n] += num[i][j];	brr[i+j] += num[i][j];}int x1, y1, x2, y2;ll Max1 = -1, Max2 = -1;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++) {if (abs(i+j) % 2 == 0) {if (Max1 < arr[i-j+n] + brr[i+j] - num[i][j]) {Max1 = arr[i-j+n] + brr[i+j] - num[i][j];x1 = i, y1 = j;}}if (abs(i+j) % 2 == 1) {if (Max2 < arr[i-j+n] + brr[i+j] - num[i][j]) {Max2 = arr[i-j+n] + brr[i+j] - num[i][j];x2 = i, y2 = j;}}}cout << Max1+Max2 << endl;printf("%d %d %d %d\n", x1, y1, x2, y2);return 0;
}


这篇关于codeforces C#264. Gargari and Bishops的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1034225

相关文章

C# 比较两个list 之间元素差异的常用方法

《C#比较两个list之间元素差异的常用方法》:本文主要介绍C#比较两个list之间元素差异,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. 使用Except方法2. 使用Except的逆操作3. 使用LINQ的Join,GroupJoin

C#如何去掉文件夹或文件名非法字符

《C#如何去掉文件夹或文件名非法字符》:本文主要介绍C#如何去掉文件夹或文件名非法字符的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#去掉文件夹或文件名非法字符net类库提供了非法字符的数组这里还有个小窍门总结C#去掉文件夹或文件名非法字符实现有输入字

C#之List集合去重复对象的实现方法

《C#之List集合去重复对象的实现方法》:本文主要介绍C#之List集合去重复对象的实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C# List集合去重复对象方法1、测试数据2、测试数据3、知识点补充总结C# List集合去重复对象方法1、测试数据

C#实现将Office文档(Word/Excel/PDF/PPT)转为Markdown格式

《C#实现将Office文档(Word/Excel/PDF/PPT)转为Markdown格式》Markdown凭借简洁的语法、优良的可读性,以及对版本控制系统的高度兼容性,逐渐成为最受欢迎的文档格式... 目录为什么要将文档转换为 Markdown 格式使用工具将 Word 文档转换为 Markdown(.

Java调用C#动态库的三种方法详解

《Java调用C#动态库的三种方法详解》在这个多语言编程的时代,Java和C#就像两位才华横溢的舞者,各自在不同的舞台上展现着独特的魅力,然而,当它们携手合作时,又会碰撞出怎样绚丽的火花呢?今天,我们... 目录方法1:C++/CLI搭建桥梁——Java ↔ C# 的“翻译官”步骤1:创建C#类库(.NET

C#代码实现解析WTGPS和BD数据

《C#代码实现解析WTGPS和BD数据》在现代的导航与定位应用中,准确解析GPS和北斗(BD)等卫星定位数据至关重要,本文将使用C#语言实现解析WTGPS和BD数据,需要的可以了解下... 目录一、代码结构概览1. 核心解析方法2. 位置信息解析3. 经纬度转换方法4. 日期和时间戳解析5. 辅助方法二、L

使用C#删除Excel表格中的重复行数据的代码详解

《使用C#删除Excel表格中的重复行数据的代码详解》重复行是指在Excel表格中完全相同的多行数据,删除这些重复行至关重要,因为它们不仅会干扰数据分析,还可能导致错误的决策和结论,所以本文给大家介绍... 目录简介使用工具C# 删除Excel工作表中的重复行语法工作原理实现代码C# 删除指定Excel单元

C#使用MQTTnet实现服务端与客户端的通讯的示例

《C#使用MQTTnet实现服务端与客户端的通讯的示例》本文主要介绍了C#使用MQTTnet实现服务端与客户端的通讯的示例,包括协议特性、连接管理、QoS机制和安全策略,具有一定的参考价值,感兴趣的可... 目录一、MQTT 协议简介二、MQTT 协议核心特性三、MQTTNET 库的核心功能四、服务端(BR

C#继承之里氏替换原则分析

《C#继承之里氏替换原则分析》:本文主要介绍C#继承之里氏替换原则,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#里氏替换原则一.概念二.语法表现三.类型检查与转换总结C#里氏替换原则一.概念里氏替换原则是面向对象设计的基本原则之一:核心思想:所有引py

C#实现访问远程硬盘的图文教程

《C#实现访问远程硬盘的图文教程》在现实场景中,我们经常用到远程桌面功能,而在某些场景下,我们需要使用类似的远程硬盘功能,这样能非常方便地操作对方电脑磁盘的目录、以及传送文件,这次我们将给出一个完整的... 目录引言一. 远程硬盘功能展示二. 远程硬盘代码实现1. 底层业务通信实现2. UI 实现三. De