General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
9844414 Contestant:
P_Nyagolov
514D - 31 GNU C++ Accepted 717 ms 16940 KB 2015-02-14 20:47:50 2015-02-14 21:54:49
 
 
→ Source
/*
ID: untamed
PROG: D
LANG: C++
*/

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<limits>
#include<climits>
#include<cmath>
#include<functional>
#include<ctime>
#include<cstdlib>
#include<fstream>
#include<typeinfo>

using namespace std;

const int ONE = 1<<10;
const int TWO = 1<<11;
const int FOUR = 1<<12;
const int EIGHT = 1<<13;
const int SIXTEEN = 1<<14;
const int THIRTY = 1<<15;
const int SIXTY = 1<<16;
const int ONE_HUNDRED = 1<<17;
const int TWO_HUNDRED = 1<<18;
const int FIVE_HUNDRED = 1<<19;
const int MILLION = 1<<20;

typedef long long int ll;
typedef short int i16;
typedef unsigned long long int u64;
typedef unsigned int u32;
typedef unsigned short int u16;
typedef unsigned char u8;

void reads(string &s)
{
    char c;
    s.clear();
    while(true)
    {
        c=getchar();
        if(c!=' ' && c!='\n')
        {
            s+=c;
            break;
        }
    }
    while(true)
    {
        c=getchar();
        if(c!=' ' && c!='\n')
            s+=c;
        else
            break;
    }
}

void prints(string s)
{
    int i,sz=s.size();
    for(i=0;i<sz;i++)
        printf("%c", s[i]);
}

string takes(string s, int from, int to)
{
    int i;
    string ans;
    ans.clear();
    for(i=from;i<=to;i++)
        ans+=s[i];
    return ans;
}

int arr[ONE_HUNDRED];

struct segment_tree
{
    int tree[FIVE_HUNDRED];

    void Initialize()
    {
        memset(tree,0,sizeof(tree));
    }

    void Build_tree(int a, int b, int node)
    {
        if(a>b)
            return;
        if(a==b)
        {
            tree[node]=arr[a];
            return;
        }
        Build_tree(a,(a+b)>>1,node<<1);
        Build_tree(((a+b)>>1)+1,b,(node<<1)|1);
        tree[node]=max(tree[node<<1],tree[(node<<1)|1]);
    }

    int Query_tree(int a, int b, int i, int j, int node)
    {
        if(a>b || a>j || b<i)
            return 0;
        if(a>=i && b<=j)
            return tree[node];
        int q1,q2;
        q1=Query_tree(a,(a+b)>>1,i,j,node<<1);
        q2=Query_tree(((a+b)>>1)+1,b,i,j,(node<<1)|1);
        return max(q1,q2);
    }
}s[6];

int n,m,k;

int a[ONE_HUNDRED][8];

void input()
{
    scanf("%d %d %d", &n, &m, &k);
    int i,j;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            scanf("%d", &a[i][j]);
        }
    }
}

bool check(int l)
{
    int all_shots;
    int from,to,i;
    all_shots=0;
    for(from=1;(to=from+l-1)<=n;from++)
    {
        all_shots=0;
        for(i=1;i<=m;i++)
        {
            all_shots+=s[i].Query_tree(1,n,from,to,1);
        }
        if(all_shots<=k)
            return true;
    }
    return false;
}

void solve()
{
    int i,j;
    for(i=1;i<=m;i++)
    {
        for(j=1;j<=n;j++)
        {
            arr[j]=a[j][i];
        }
        s[i].Build_tree(1,n,1);
    }
    //printf("%d %d\n", s[1].Query_tree(1,n,2,4,1), s[2].Query_tree(1,n,2,4,1));
    int left,right,middle;
    left=0;
    right=n+1;
    while(right-left>1)
    {
        middle=(left+right)>>1;
        if(check(middle))
            left=middle;
        else
            right=middle;
    }
    int all_shots;
    int from,to,l=left;
    all_shots=0;
    for(from=1;(to=from+l-1)<=n;from++)
    {
        all_shots=0;
        for(i=1;i<=m;i++)
        {
            all_shots+=s[i].Query_tree(1,n,from,to,1);
        }
        if(all_shots<=k)
        {
            for(i=1;i<=m;i++)
            {
                if(i>1)
                    printf(" ");
                printf("%d", s[i].Query_tree(1,n,from,to,1));
            }
            printf("\n");
            return;
        }
    }
}

int main()
{
    input();
    solve();
    return 0;
}
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details