Codeforces Round #291 Div2 D
An army of n droids is lined up in one row. Each droid is described by m integers a1, a2, ..., am , where ai is the number of details of the i -th type in this droid’s mechanism. R2−D2 wants to destroy the sequence of consecutive droids of maximum length. He has m weapons, the i -th weapon can affect all the droids in the army by destroying one detail of the i -th type (if the droid doesn’t have details of this type, nothing happens to it).
A droid is considered to be destroyed when all of its details are destroyed. R2−D2 can make at most k shots. How many shots from the weapon of what type should R2−D2 make to destroy the sequence of consecutive droids of maximum length?
Limits
TimeLimit(ms):2000
MemoryLimit(MB):256
n∈[1,105]
m∈[1,5]
k∈[0,109]
ai∈[0,108]
Look up Original Problem From here
Solution
to - pointers 방법 으로 포인터 l = 1, r = 1 을 설정 합 니 다.t = ∑ mj = 1max (alj,..., arj) 를 구하 는데 그 중에서 aij 는 i 개인의 j 번 째 속성 을 나타 낸다.t > = k 면 r + +, 그렇지 않 으 면 l + (보증 l < = r), 이 과정 에서 r - l + 1 의 최고 치 를 계속 유지 합 니 다...
Complexity
TimeComplexity:O(N×M×log2N)
MemoryComplexity:O(N×M)
My Code
//Hello. I'm Peter.
#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<cctype>
#include<ctime>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define peter cout<<"i am peter"<<endl
#define input freopen("data.txt","r",stdin)
#define randin srand((unsigned int)time(NULL))
#define INT (0x3f3f3f3f)*2
#define LL (0x3f3f3f3f3f3f3f3f)*2
#define gsize(a) (int)a.size()
#define len(a) (int)strlen(a)
#define slen(s) (int)s.length()
#define pb(a) push_back(a)
#define clr(a) memset(a,0,sizeof(a))
#define clr_minus1(a) memset(a,-1,sizeof(a))
#define clr_INT(a) memset(a,INT,sizeof(a))
#define clr_true(a) memset(a,true,sizeof(a))
#define clr_false(a) memset(a,false,sizeof(a))
#define clr_queue(q) while(!q.empty()) q.pop()
#define clr_stack(s) while(!s.empty()) s.pop()
#define rep(i, a, b) for (int i = a; i < b; i++)
#define dep(i, a, b) for (int i = a; i > b; i--)
#define repin(i, a, b) for (int i = a; i <= b; i++)
#define depin(i, a, b) for (int i = a; i >= b; i--)
#define pi acos(-1.0)
#define eps 1e-9
#define MOD 1000000007
#define MAXN 100100
#define N
#define M 6
int n,m,k;
int matrix[MAXN][M];
struct Segment_Tree{
int left,right;
ll max;
}tree[MAXN<<2][M];
void plant_tree(int id,int l,int r,int c){
tree[id][c].left=l,tree[id][c].right=r;
if(l==r){
tree[id][c].max=matrix[l][c];
return;
}
int mid=(l+r)>>1;
plant_tree(id<<1,l,mid,c);
plant_tree(id<<1|1,mid+1,r,c);
tree[id][c].max=max(tree[id<<1][c].max,tree[id<<1|1][c].max);
}
ll query_max(int id,int l,int r,int c){
if(tree[id][c].left==l && tree[id][c].right==r){
return tree[id][c].max;
}
int mid=(tree[id][c].left+tree[id][c].right)>>1;
if(r<=mid) return query_max(id<<1,l,r,c);
else if(mid<l) return query_max(id<<1|1,l,r,c);
else return max(query_max(id<<1,l,mid,c),query_max(id<<1|1,mid+1,r,c));
}
ll query(int l,int r){
ll res=0;
repin(j,1,m){
res+=query_max(1,l,r,j);
}
return res;
}
int ansl,ansr,ansnum;
int main(){
scanf("%d %d %d",&n,&m,&k);
repin(i,1,n){
repin(j,1,m){
scanf("%d",&matrix[i][j]);
}
}
repin(j,1,m){
plant_tree(1,1,n,j);
}
//two-pointers;
int l=1,r=1;
ansnum=-1;
while(r<=n){
ll t=query(l,r);
if(t>k){
l++;
while(l>r) r++;
continue;
}
if(r-l+1>ansnum){
ansl=l,ansr=r;
ansnum=r-l+1;
}
r++;
}
if(ansnum==-1){
repin(j,1,m){
if(j!=1) printf(" ");
printf("%d",0);
}
printf("
");
exit(0);
}
repin(j,1,m){
ll t=query_max(1,ansl,ansr,j);
if(j!=1) printf(" ");
printf("%I64d",t);
}
printf("
");
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.