#26

by asd

Submitted 4 years 10 months 1 day ago
Tue Jan 14 22:36:13 CST 2020
Judger: ZJS
Dataset Version: v0

92 ms / 42500 KB
Final 0
Problem: lss1.trifang
Language: GNU C++ 11


#1

0ms / 6916KB / Accepted
Input
2 8 1
26500 19169 15724 11478 29358 26962 24464 5705 
28145 23281 16827 9961 491 2995 11942 4827 
Output
29358
Answer
29358
Checker Information
"29358"

#2

15ms / 6912KB / Accepted
Input
7 2 1
3902 153 
292 12382 
17421 18716 
19718 19895 
5447 21726 
14771 11538 
1869 19912 
Output
21726
Answer
21726
Checker Information
"21726"

#3

15ms / 6916KB / Accepted
Input
8 10 4
9894 28703 23811 31322 30333 17673 4664 15141 7711 28253 
6868 25547 27644 32662 32757 20037 12859 8723 9741 27529 
778 12316 3035 22190 1842 288 30106 9040 8942 19264 
22648 27446 23805 15890 6729 24370 15350 15006 31101 24393 
3548 19629 1262<...>
Output
336998
Answer
336998
Checker Information
"336998"

#4

0ms / 6916KB / Accepted
Input
3 7 1
9161 18636 22355 24767 23655 15574 4031 
12052 27350 1150 16941 21724 13966 3430 
31107 30191 18007 11337 15457 12287 27753 
Output
31107
Answer
31107
Checker Information
"31107"

#5

31ms / 6916KB / Wrong Answer
Input
4 6 2
32209 9758 24221 18588 6422 24946 
27506 13030 16413 29168 900 32591 
18762 1655 17410 6359 27624 20537 
21548 6483 27595 4041 3602 24350 
Output
71074
Answer
105102
Checker Information
1st words differ - expected: '105102', found: '71074'

#1

15ms / 6916KB / Accepted
Input
42 68 14
26500 19169 15724 11478 29358 26962 24464 5705 28145 23281 16827 9961 491 2995 11942 4827 5436 32391 14604 3902 153 292 12382 17421 18716 19718 19895 5447 21726 14771 11538 1869 19912 25667 26299 17035 9894 28703 23811 31322 30333 17673 4664 1514<...>
Output
3489234
Answer
3489234
Checker Information
"3489234"

#2

15ms / 6920KB / Wrong Answer
Input
93 65 26
18866 14693 30664 23775 13000 12212 21100 7551 25476 6379 10943 17877 3789 361 11385 8272 11434 15144 29561 25563 14504 12946 23888 20308 12157 1430 5123 6464 4074 4346 13837 1981 25318 26611 16292 17591 3832 27123 6461 16991 31461 27330 28498 17<...>
Output
11543750
Answer
11572908
Checker Information
1st words differ - expected: '11572908', found: '11543750'

#1

31ms / 9520KB / Accepted
Input
42 468 14
26500 19169 15724 11478 29358 26962 24464 5705 28145 23281 16827 9961 491 2995 11942 4827 5436 32391 14604 3902 153 292 12382 17421 18716 19718 19895 5447 21726 14771 11538 1869 19912 25667 26299 17035 9894 28703 23811 31322 30333 17673 4664 151<...>
Output
3628190
Answer
3628190
Checker Information
"3628190"

#2

92ms / 36940KB / Accepted
Input
396 779 34
18689 32264 15410 19108 25202 14285 28381 15349 30402 13648 27958 27012 19594 4058 25652 8696 14115 20334 30106 4760 14090 6562 31612 3259 31113 17070 9471 16255 31636 29891 20576 14782 21490 24990 17976 18494 26781 12892 14846 1064 4970 10640 <...>
Output
20373162
Answer
20373162
Checker Information
"20373162"

#3

61ms / 28852KB / Accepted
Input
310 681 61
2959 31511 24294 7351 26164 1245 27572 4648 25487 24577 7142 2807 29239 2322 24800 15814 3539 28262 2988 9034 18641 8964 17481 24659 7771 14528 2885 4358 8326 1448 31118 22893 22221 22687 12933 24371 24767 24904 15444 4264 12532 20262 12929 238<...>
Output
63173817
Answer
63173817
Checker Information
"63173817"

#4

61ms / 42500KB / Wrong Answer
Input
725 442 311
11037 8735 2990 22511 14925 22528 8687 18110 19826 8996 18706 29929 8305 14565 26071 26051 21666 29514 28665 24750 18485 23258 9392 27020 31950 690 17018 7543 20851 27350 12827 18354 5032 23749 16610 17119 11224 30288 20527 31346 26871 22187 7<...>
Output
0
Answer
1587819050
Checker Information
1st words differ - expected: '1587819050', found: '0'
/*
Though leaves are many, the root is one;
Through all the lying days of my youth
I swayed my leaves and flowers in the sun,
Now may I wither into the truth.
 
- William Butler Yeats
*/
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <cstdio>
#include <vector>
#include <set>
#include <cassert>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <functional>
#include <iomanip>
#include <bitset>
//#include <windows.h>  //Should be deleted when using AtCoder&POJ
using namespace std;
 
#define ll long long
#define pii pair<int,int>
#define qi ios::sync_with_stdio(0)
#define dbg if(false)
/**==Info==
*Program:1
*Problem:Rhombus
*Date:2019-12-30
*Algorithm:My rubbish prefix sum and violence
*Status:Unknown*/
 
bool debug=false;
 
ll n,m,k;
ll a[1005][1005];
ll tri[4][1005][1005];
 
ll colsum[1005][1005],rowsum[1005][1005];
 
int dsuid[1005][1005],dsuind[1005][1005];
ll dsusum[2005][2005];
int dsdid[1005][1005],dsdind[1005][1005];
ll dsdsum[2005][2005];
ll f[1005][1005];
 
int dsuic,dsdic;
 
const int L=0,R=1;
 
void runDsu(int x,int y){
	int cnt=0;
	
	while(true){
		dsuid[x][y]=dsuic;
		dsuind[x][y]=cnt;
		dsusum[dsuic][cnt]=(cnt==0?0:dsusum[dsuic][cnt-1])+a[x][y];
		cnt++;
		x--;y++;
		if(x<0 || y>=m){
			break;
		}
	}
	dsuic++;
}
 
void runDsd(int x,int y){
	int cnt=0;
	
	while(true){
		dsdid[x][y]=dsdic;
		dsdind[x][y]=cnt;
		dsdsum[dsdic][cnt]=(cnt==0?0:dsdsum[dsdic][cnt-1])+a[x][y];
		cnt++;
		x++;y++;
		if(x>=n || y>=m){
			break;
		}
	}
	dsdic++;
}
 
inline ll getCS(int col,int st,int ed){
	if(st>ed){
		swap(st,ed);
	}
	
	return colsum[col][ed]-(st==0?0:colsum[col][st-1]);
}
 
//inline int getDSUId(int x,int y){
//	return dsuid[x][y];
//}
//
//inline int getDSUInd(int x,int y){
//	return dsuind[x][y];
//}
//
//inline int getDSDId(int x,int y){
//	return dsdid[x][y];
//}
//
//inline int getDSDInd(int x,int y){
//	return dsdind[x][y];
//}
 
inline ll getDSU(int id,int st,int ed){
	if(st>ed){
		swap(st,ed);
	}
	
	return dsusum[id][ed]-(st==0?0:dsusum[id][st-1]);
}
 
inline ll getDSD(int id,int st,int ed){
	if(st>ed){
		swap(st,ed);
	}
	
	return dsdsum[id][ed]-(st==0?0:dsdsum[id][st-1]);
}
 
inline ll getDSU(int x1,int y1,int x2,int y2){
	dbg cout<<"DSU="<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<" "<<dsuid[x1][y1]<<" "<<dsuid[x2][y2]<<endl;
	
	assert(dsuid[x1][y1]==dsuid[x2][y2]);
	return getDSU(dsuid[x1][y1],dsuind[x1][y1],dsuind[x2][y2]);
}
inline ll getDSD(int x1,int y1,int x2,int y2){
	dbg cout<<"DSD="<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<" "<<dsdid[x1][y1]<<" "<<dsdid[x2][y2]<<endl;
	assert(dsdid[x1][y1]==dsdid[x2][y2]);
	return getDSD(dsdid[x1][y1],dsdind[x1][y1],dsdind[x2][y2]);
}
 
inline ll getRS(int rownum,int l,int r){
	if(l>r){
		swap(l,r);
	}
	
	return rowsum[rownum][r]-(l==0?0:rowsum[rownum][l-1]);
}
 
void proceedL(){
	
	for(int i=k-1;i<=n-k;i++){
		int up=k-1;
		for(int j=0;j<k;j++){
			tri[L][i][k-1]+=getCS(k-1-j,i-up,i+up);
			up--;
		}
	}
	
	
	for(int i=k-1;i<=n-k;i++){
		dbg cout<<"Doing line "<<i<<endl;
		for(int j=k;j<=m-k;j++){
			dbg cout<<"Solving for column "<<j<<endl;
			
			ll p1=tri[L][i][j-1];
			ll p2=getCS(j,i-k+1,i+k-1);
			ll p3=getDSU(i,j-k,i-k+1,j-1);
			ll p4=getDSD(i,j-k,i+k-1,j-1);
			ll p5=a[i][j-k];
			
			dbg cout<<i<<" "<<j<<" p="<<p1<<" "<<p2<<" "<<p3<<" "<<p4<<" "<<p5<<endl;
			tri[L][i][j]=p1+p2-p3-p4+p5;
		}
		
	}
	
//	dbg{
		ll mx=0; 
		for(int i=k-1;i<=n-k;i++){
			for(int j=k-1;j<=m-k;j++){
				mx=max(mx,tri[L][i][j]);
			}
		}
		cout<<mx<<endl;
		exit(0);
//	}
}
 
void proceedR(){
	
	for(int i=k-1;i<=n-k;i++){
		int up=k-1;
		for(int j=0;j<k;j++){
			tri[R][i][k-1]+=getCS(k-1+j,i-up,i+up);
			up--;
		}
	}
	
	
	for(int i=k-1;i<=n-k;i++){
		dbg cout<<"Doing line "<<i<<endl;
		for(int j=k;j<=m-k;j++){
			dbg cout<<"Solving for column "<<j<<endl;
			
			ll p1=tri[R][i][j-1];
			ll p2=getCS(j-1,i-k+1,i+k-1);
			ll p3=getDSD(i,j+k-1,i-k+1,j);
			ll p4=getDSU(i,j+k-1,i+k-1,j);
			ll p5=a[i][j+k-1];
			
			dbg cout<<i<<" "<<j<<" p="<<p1<<" "<<p2<<" "<<p3<<" "<<p4<<" "<<p5<<endl;
			tri[R][i][j]=p1-p2+p3+p4-p5;
		}
		
	}
	
	dbg{
		for(int i=k-1;i<=n-k;i++){
			for(int j=k-1;j<=m-k;j++){
				cout<<tri[R][i][j]<<" ";
			}
			cout<<endl;
		}
	}
}
 
int main(int argc,char* argv[]){
	qi;
	cin>>n>>m>>k;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>a[i][j];
		}
	}
	
	//calc for the col sum
	for(int i=0;i<m;i++){
		colsum[i][0]=a[0][i];
		for(int j=1;j<n;j++){
			colsum[i][j]=colsum[i][j-1]+a[j][i];
		}
	}
	
	for(int i=0;i<n;i++){
		rowsum[i][0]=a[i][0];
		for(int j=1;j<m;j++){
			rowsum[i][j]=rowsum[i][j-1]+a[i][j];
		}
	}
	
	//calc for the dsu
	for(int i=0;i<n;i++){
		runDsu(i,0);
	}
	for(int i=1;i<m;i++){
		runDsu(n-1,i);
	}
	
	dbg{
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				printf("(%d,%d) in dsu %d ind= %d sum_until=%d\t",i,j,dsuid[i][j],dsuind[i][j],dsusum[dsuid[i][j]][dsuind[i][j]]);
			}
			printf("\n");
		}
	}
	
	//calc for dsd
	for(int i=n-1;i>=0;i--){
		runDsd(i,0);
	}
	for(int i=1;i<m;i++){
		runDsd(0,i);
	}
	
	dbg{
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				printf("(%d,%d) in dsd %d ind= %d sum_until=%d\t",i,j,dsdid[i][j],dsdind[i][j],dsdsum[dsdid[i][j]][dsdind[i][j]]);
			}
			printf("\n");
		}
	}
	
	proceedL();
	proceedR();
	
	//calc left up corner answer
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
//			cout<<i<<' '<<j<<" "<<a[i][j]<<" "<<max(0,k-abs(i-(k-1))-abs(j-(k-1)))<<endl;
			f[k-1][k-1]+=a[i][j]*max(0ll,k-abs(i-(k-1))-abs(j-(k-1)));
		}
	}
	
	dbg cout<<"ini="<<f[k-1][k-1]<<endl;
	
	//move to the right
	for(int i=k-1;i<=n-k;i++){
		for(int j=k;j<=m-k;j++){
			//move
			ll p1=f[i][j-1];
			ll p2=tri[R][i][j];
			ll p3=tri[L][i][j-1];
			
			dbg cout<<"F "<<i<<" "<<j<<"="<<p1<<"+"<<p2<<"-"<<p3<<endl;
			f[i][j]=p1+p2-p3;
		}
		
		//move down
		if(i==n-k){
			continue;
		}
		
		ll upt=0,downt=0;
		
		int up=k-1;
		for(int j=i;j>=i-k+1;j--){
			upt+=getRS(j,k-1-up,k-1+up);
			up--;
		}
		
		int down=k-1;
		for(int j=i+1;j<=i+k;j++){
			downt+=getRS(j,k-1-down,k-1+down);
			down--;
		}
		
		dbg cout<<"F:"<<i+1<<" "<<k-1<<"="<<f[i][k-1]<<" "<<upt<<" "<<downt<<endl;
		
		
		f[i+1][k-1]=f[i][k-1]-upt+downt;	
		
	}
	
	int x=k-1,y=k-1;
	for(int i=k-1;i<=n-k;i++){
		for(int j=k-1;j<=m-k;j++){
			if(f[i][j]>f[x][y]){
				x=i;
				y=j;
			}
		}
	}
	
	cout<<x+1<<" "<<y+1<<endl;
	return 0;
}
Main.cpp: In function ‘int main(int, char**)’:
Main.cpp:268:117: warning: format ‘%d’ expects argument of type ‘int’, but argument 6 has type ‘long long int’ [-Wformat=]
     printf("(%d,%d) in dsu %d ind= %d sum_until=%d\t",i,j,dsuid[i][j],dsuind[i][j],ds<...>