Cod sursa(job #7092)

Utilizator tudalexTudorica Constantin Alexandru tudalex Data 21 ianuarie 2007 12:27:40
Problema Elimin Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasa a 10-a Marime 1.72 kb
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
using namespace std;
vector <int> a[8000];
int sr[8000],
    sc[8000],
    sr2[8000],
    sc2[8000],
    ind[8000];
int i,j,n,m,r,c;
long long max1,max2;

//Comparation functions
bool cmpf_rw ( const int x, const int y) 
{return sr[x]<sr[y];}
bool cmpf_co ( const int x, const int y) 
{return sc[x]<sc[y];}

void solve_row()
{
     int i,j;
     for (i=1;i<=n;++i) ind[i]=i;
     sort(ind+1,ind+n+1,cmpf_rw);
     for (i=1;i<=r;++i) 
     for (j=1;j<=m;++j) sc[i]-=a[i][j];
}
void solve_column()
{
     int i,j;
     for (i=1;i<=n;++i) ind[i]=i;
     sort(ind+1,ind+m+1,cmpf_co);
     for (i=1;i<=c;++i)
     for (j=1;j<=n;++j) sr[i]-=a[i][j];
}

     
void read_data()
{
     int t;
     scanf("%d %d %d %d",&n,&m,&r,&c);
     
     for (i=1;i<=n;++i) a[i].resize(m+2); //THingie that I don't know if it would work
     
     for (i=1;i<=n;++i)
     for (j=1;j<=n;++j)
     {
         scanf("%d",&a[i][j]);
         sr[i]+=a[i][j];
         sc[j]+=a[i][j];
         
     }
}
long long maxim()
{
     long long m1=0,m2=0;
     for (i=1;i<=n;++i) 
     {
         m1+=sr[i];
         m2+=sc[i];
     }
     return m1;
}     
int main()
{
    freopen("elimin.in","r",stdin);
    freopen("elimin.out","w",stdout);
    read_data();
    //First solution
    memcpy(sr2,sr,sizeof(sr));
    memcpy(sc2,sc,sizeof(sc));
    
    solve_column();
    solve_row();
    
    max1=maxim();
    
    //Second solution
    memcpy(sr,sr2,sizeof(sr2));
    memcpy(sc,sc2,sizeof(sc2));
    
    solve_row();
    solve_column();
    
    max2=maxim();
    printf("%lld\n",max1>max2?max1:max2);
    return 0;
}