D.R 2 D 2 and Droid Army(2分プラス多次元セグメントツリークエリ区間最大値)
2066 ワード
単純な線分ツリー、直接コードを付けます.
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <cstdlib>
#include <algorithm>
#define ls u << 1
#define rs u << 1 | 1
#define lson l, mid, u << 1
#define rson mid + 1, r, u << 1 | 1
#define INF 0x3f3f3f3f
#define MAX 4
using namespace std;
typedef long long ll;
const int M = 1e5 + 100;
const int mod = 2147483647;
int sum[10][M << 2],n,m,k,res[10],ans[10];
void pushup(int u){
for(int i = 0; i < m; i++)
sum[i][u] = max(sum[i][ls],sum[i][rs]);
}
void build(int l,int r,int u){
if(l == r){
for(int i = 0; i < m; i++)
scanf("%d",&sum[i][u]);
}
else{
int mid = (l + r) >> 1;
build(lson);
build(rson);
pushup(u);
}
}
void query(int L,int R,int l,int r,int u){
if(L <= l && R >= r){
for(int i = 0; i < m; i++)
res[i] = max(res[i],sum[i][u]);
}
else{
int mid = (l + r) >> 1;
if(L <= mid) query(L,R,lson);
if(R > mid) query(L,R,rson);
}
}
bool solve(int len){
for(int l = 1; l <= n - len + 1; l++){
int r = l + len - 1,sum = 0;
memset(res,-1,sizeof(res));
query(l,r,1,n,1);
for(int i = 0; i < m; i++){
sum += res[i];
}
if(sum <= k){
for(int i = 0; i < m; i++)
ans[i] = res[i];
return true;
}
}
return false;
}
int main(){
scanf("%d %d %d",&n,&m,&k);
build(1,n,1);
int l = 1,r = n;
while(l <= r){
int mid = (l + r) >> 1;
if(solve(mid)) l = mid + 1;
else r = mid - 1;
}
for(int i = 0; i < m; i++){
if(i) putchar(' ');
printf("%d",ans[i]);
}
puts("");
return 0;
}