Zerojudge c295

題敘

https://zerojudge.tw/ShowProblem?problemid=c295
給 $N$ 群數字，每群數字包含 $M$ 個正整數，從每群數字中選最大的出來加總
輸出其總和 $S$ 以及各群數字中最大值能整除 $S$ 的數字

想法

每群數字只需存最大值，接下來 $O(n)$ 判斷每個最大值是否能整除 $S$ 即可

Code

//By Koios1143
#include<bits/stdc++.h>
#define LL long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
using namespace std;
int n,m,s=0,arr[25];

int main(){
	IOS
	cin>>n>>m;
	for(int i=0 ; i<n ; i++){
		int Max=0;
		for(int j=0,tmp ; j<m ; j++){
			cin>>tmp;
			Max=max(Max,tmp);
		}
		arr[i]=Max;
		s+=Max;
	}
	cout<<s<<'\n';
	bool found = false;
	for(int i=0 ; i<n ; i++){
		if(s%arr[i] == 0){
			if(found) cout<<' ';
			else found=true;
			cout<<arr[i];
		}
	}
	if(!found) cout<<"-1";
	cout<<'\n';
	return 0;
}

複雜度

$O(n)$