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#实现MQTT通信实战

《基于C#实现MQTT通信实战》MQTT消息队列遥测传输,在物联网领域应用的很广泛,它是基于Publish/Subscribe模式,具有简单易用,支持QoS,传输效率高的特点,下面我们就来看看C#实现... 目录1、连接主机2、订阅消息3、发布消息MQTT(Message Queueing Telemetr

C#特性(Attributes)和反射(Reflection)详解

《C#特性(Attributes)和反射(Reflection)详解》:本文主要介绍C#特性(Attributes)和反射(Reflection),具有很好的参考价值,希望对大家有所帮助,如有错误... 目录特性特性的定义概念目的反射定义概念目的反射的主要功能包括使用反射的基本步骤特性和反射的关系总结特性

C#实现查找并删除PDF中的空白页面

《C#实现查找并删除PDF中的空白页面》PDF文件中的空白页并不少见,因为它们有可能是作者有意留下的,也有可能是在处理文档时不小心添加的,下面我们来看看如何使用Spire.PDFfor.NET通过C#... 目录安装 Spire.PDF for .NETC# 查找并删除 PDF 文档中的空白页C# 添加与删

通过C#获取Excel单元格的数据类型的方法详解

《通过C#获取Excel单元格的数据类型的方法详解》在处理Excel文件时,了解单元格的数据类型有助于我们正确地解析和处理数据,本文将详细介绍如何使用FreeSpire.XLS来获取Excel单元格的... 目录引言环境配置6种常见数据类型C# 读取单元格数据类型引言在处理 Excel 文件时,了解单元格

C#实现高性能Excel百万数据导出优化实战指南

《C#实现高性能Excel百万数据导出优化实战指南》在日常工作中,Excel数据导出是一个常见的需求,然而,当数据量较大时,性能和内存问题往往会成为限制导出效率的瓶颈,下面我们看看C#如何结合EPPl... 目录一、技术方案核心对比二、各方案选型建议三、性能对比数据四、核心代码实现1. MiniExcel

在.NET平台使用C#为PDF添加各种类型的表单域的方法

《在.NET平台使用C#为PDF添加各种类型的表单域的方法》在日常办公系统开发中,涉及PDF处理相关的开发时,生成可填写的PDF表单是一种常见需求,与静态PDF不同,带有**表单域的文档支持用户直接在... 目录引言使用 PdfTextBoxField 添加文本输入域使用 PdfComboBoxField

C#如何调用C++库

《C#如何调用C++库》:本文主要介绍C#如何调用C++库方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录方法一:使用P/Invoke1. 导出C++函数2. 定义P/Invoke签名3. 调用C++函数方法二:使用C++/CLI作为桥接1. 创建C++/CL

C#使用StackExchange.Redis实现分布式锁的两种方式介绍

《C#使用StackExchange.Redis实现分布式锁的两种方式介绍》分布式锁在集群的架构中发挥着重要的作用,:本文主要介绍C#使用StackExchange.Redis实现分布式锁的... 目录自定义分布式锁获取锁释放锁自动续期StackExchange.Redis分布式锁获取锁释放锁自动续期分布式

C# foreach 循环中获取索引的实现方式

《C#foreach循环中获取索引的实现方式》:本文主要介绍C#foreach循环中获取索引的实现方式,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、手动维护索引变量二、LINQ Select + 元组解构三、扩展方法封装索引四、使用 for 循环替代

C# Where 泛型约束的实现

《C#Where泛型约束的实现》本文主要介绍了C#Where泛型约束的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录使用的对象约束分类where T : structwhere T : classwhere T : ne