Alim is here

1. Various

Code1

code2

Post3

#include <stdio.h>
#define max(a,b) (a>b)?a:b
int sum[100][100];
int inf = 1<<25;
int SUM(int si,int sj,int ei,int ej)
{
    int res = sum[ei][ej];
    if(sj-1>=0)
        res-=sum[ei][sj-1];
    if(si-1>=0)
        res-=sum[si-1][ej];
    if(si-1>=0&&sj-1>=0)
        res+=sum[si-1][sj-1];
    return res;
}
int main()
{
    int i,j,y,x,N,M,m,c;
    char buffer[100];
    scanf("%d",&c);
    getchar();
    getchar();
    while(c--)
    {
        N = 0;
        M = 0;
        while(gets(buffer)&&buffer[0])
        {
            for(M=0;buffer[M];M++)
                sum[N][M]=buffer[M]-'0';
            N++;
        }
        for(i=0;i<N;i++)
            for(j=1;j<M;j++)
                sum[i][j]+=sum[i][j-1];
        for(i=0;i<M;i++)
            for(j=1;j<N;j++)
                sum[j][i]+=sum[j-1][i];
        m = 0;
        for(i=0;i<N;i++)
            for(j=0;j<M;j++)
                for(y=i;y<N;y++)
                    for(x=j;x<M;x++)
                        if(SUM(i,j,y,x)==(y-i+1)*(x-j+1))
                            m = max(m,(y-i+1)*(x-j+1));
        printf("%d\n",m);
        if(c)
            putchar('\n');
    }
    return 0;
}

CODE

#include<bits/stdc++.h>
using namespace std;

int a[105][105],cu[105][105];
int main()
{
    int i,j,k,n,m,d,test;
    cin>>test;
    getchar();
    getchar();
    while(test--)
    {
        i=0;
        while(1)
        {
            i++;
            string s;
            getline(cin,s);
            if(s=="") break;
            n=s.size();
            for(j=0;j<n;j++)
            {
                if(s[j]=='0') a[i][j+1]=-100001;
                else a[i][j+1]=1;
            }
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
                cu[i][j]=cu[i][j-1]+a[j][i];
        }
        long long max_sum=0,sum;
        for(i=1;i<=n;i++)
        {
            for(j=i;j<=n;j++)
            {
                sum=0;
                for(k=1;k<=n;k++)
                {
                    sum=sum+cu[k][j]-cu[k][i-1];
                    if(sum<0) sum=0;
                    max_sum=max(sum,max_sum);
                }
            }
        }


        long long final_max_sum=max_sum;
        max_sum=0;
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(a[i][j]==0) a[i][j]=1;
                else a[i][j]=-100001;
            }
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
                cu[i][j]=cu[i][j-1]+a[j][i];
        }
        for(i=1;i<=n;i++)
        {
            for(j=i;j<=n;j++)
            {
                sum=0;
                for(k=1;k<=n;k++)
                {
                    sum=sum+cu[k][j]-cu[k][i-1];
                    if(sum<0) sum=0;
                    max_sum=max(sum,max_sum);
                }
            }
        }
        final_max_sum=max(max_sum,final_max_sum);
        cout<<final_max_sum<<endl;
        if(test) puts("");
    }
    return 0;
}

Efficient Way to Find Sum of Divisor(SOD)

Imagine you wish to work out the sum of divisors of the number 72. It would not take long to list the divisors, and then find their sum: 1 + 2 + 3 + 4 + 6 + 8 + 9 + 12 + 18 + 24 + 36 + 72 = 195.

However, this method would become both tedious and difficult for large numbers like 145600. Fortunately, there is a simple and elegant method at hand.

Let σ(n) be the sum of divisors of the natural number, n.

For any prime, p: σ(p) = p + 1, as the only divisors would be 1 and p.

Consider pa: σ(pa) = 1 + p + p2 + … + pa (1).

Multiplying by p: pσ(pa) = p + p2 + p3 + … + pa + 1 (2).

Subtracting (1) from (2): pσ(pa)−σ(pa) = (p−1)σ(pa) = pa+1 − 1.

Hence σ(pa) = (pa+1 − 1)/(p − 1).

For example, σ(34)=(35−1)/(3−1) = 242/2 = 121,
and checking: 1 + 3 + 9 + 27 + 81 = 121.

Although no proof is supplied here, the usefulness of the function, σ(n), is its multiplicity, which means that σ(a×b×…)=σ(a)×σ(b)×…, where a, b, …, are relatively prime.

Returning to example, we use the fact that σ(72) = σ(23×32). As 23 and 32 are relatively prime, we can separately work out σ(23) = 24 − 1 = 15 and σ(32) = (33 − 1)/2 = 13. Therefore, σ(72) = 15×13 = 195.

Related Problem: Lightoj-1054