Light OJ 1164 Horrible Queries

#include<bits/stdc++.h>
#define mx 100009
using namespace std;
typedef long long ll;
struct s
{
    ll sum,prop;
}tree[4*mx];
ll arr[100009];
void init(int node,int b,int e)
{
    if (b==e)
    {
        tree[node].sum=arr[b];
        tree[node].prop=0;
        return;
    }
    int Left=node*2;
    int Right=(node*2)+1;
    int mid=(b+e)/2;
    init(Left,b,mid);
    init(Right,mid+1,e);
    tree[node].sum=tree[Left].sum + tree[Right].sum;
    tree[node].prop=0;
}
void update(int node,int b,int e,int i,int j,ll x)
{
    if(i>e||j<b)
        return;
    if(b>=i&&e<=j)
    {
        tree[node].prop+=x;
        tree[node].sum+=(e-b+1)*x;
        return;
    }
    ll Left=node*2;
    ll Right=(node*2)+1;
    ll mid=(b+e)/2;
    update(Left,b,mid,i,j,x);
    update(Right,mid+1,e,i,j,x);
    tree[node].sum=tree[Left].sum+tree[Right].sum+(e-b+1)*tree[node].prop;
}
ll query(int node,int b,int e,int i,int j,ll carry=0)
{
    if(i>e||j<b)
        return 0;
    if (b>=i&&e<=j)
    {
        return tree[node].sum+carry*(e-b+1);
    }
    int Left=node<<1;
    int Right=(node<<1)+1;
    int mid=(b+e)>>1;
    ll p1=query(Left,b,mid,i,j,carry+tree[node].prop);
    ll p2=query(Right,mid+1,e,i,j,carry+tree[node].prop);
    return p1+p2;
}
int main()
{
    int i,j,k,l,m,n,test;
    scanf("%lld",&test);
    for(m=1;m<=test;m++)
    {
        scanf("%d%d",&n,&k);
        printf("Case %d:\n",m);
        memset(arr,0,sizeof(arr));
        init(1,1,n);
        for(i=0;i<k;i++)
        {
            int op;
            scanf("%d",&op);
            if(op==0)
            {
                int st,ed,vl;
                scanf("%d%d%lld",&st,&ed,&vl);
                update(1,1,n,st+1,ed+1,vl);
            }
            if(op==1)
            {
                int st,ed;
                scanf("%d%d",&st,&ed);
                ll y=query(1,1,n,st+1,ed+1);
                printf("%lld\n",y);
            }
        }
    }
    return 0;
}

Light OJ 1025 - The Specials Menu

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll arr[100];
ll dp[100][100];
ll l,n;
string s;
ll solve(ll i,ll j)
{
    if(i>j)
        return 0;
    if(i==j)
        return 1;
    if(dp[i][j]!=-1)
        return dp[i][j];
    if(s[i]==s[j])
    {
        dp[i][j]=1+solve(i+1,j)+solve(i,j-1);
    }
    if(s[i]!=s[j])
    {
        dp[i][j]=solve(i+1,j)+solve(i,j-1)-solve(i+1,j-1);
    }
    return dp[i][j];
}
int main()
{
    ll i,j,k,m,n,test;
    cin>>test;
    for(k=1;k<=test;k++)
    {
        cin>>s;
        memset(dp,-1,sizeof(dp));
        l=s.size();
        cout<<"Case "<<k<<": "<<solve(0,l-1)<<endl;
    }
    return 0;
}

BFS in a 3D grid

#include<bits/stdc++.h>
using namespace std;
int graph[35][35][35];
int visited[35][35][35];
int level[35][35][35];
int x[6]={1,-1,0,0,0,0};
int y[6]={0,0,1,-1,0,0};
int z[6]={0,0,0,0,1,-1};
int main()
{
    int r,c,w;
    cin>>w>>r>>c;//w:how many levels,c:row in each level,c:column in each level
    memset(graph,0,sizeof(graph));
    for(int i=0;i<w;i++)
    {
        for(int j=0;j<r;j++)
        {
            for(int k=0;k<c;k++)
            {
                cin>>graph[i][j][k];//use 1 and 0 as input
            }
        }
    }
    memset(visited,0,sizeof(visited));
    memset(level,0,sizeof(level));
    queue<int>q;
    int stx,sty,stz,enx,eny,enz;
    cin>>stx>>sty>>stz;
    cin>>enx>>eny>>enz;
    visited[stx][sty][stz]=true;
    level[stx][sty][stz]=0;
    q.push(stx);
    q.push(sty);
    q.push(stz);
    int ans;
    bool flag=0;
    while(!q.empty())
    {
        int f1,f2,f3;
        f1=q.front();
        q.pop();
        f2=q.front();
        q.pop();
        f3=q.front();
        q.pop();
        for(int in=0;in<6;in++)
        {
            int v1,v2,v3;
            v1=f1+x[in];
            v2=f2+y[in];
            v3=f3+z[in];
            if(!visited[v1][v2][v3]&&!level[v1][v2][v3]&&graph[v1][v2][v3]==1&&(v1>=0&&v1<w&&v2>=0&&v2<r&&v3>=0&&v3<c))
            {
                {
                    level[v1][v2][v3]=level[f1][f2][f3]+1;
                    //cout<<"LEVEL:"<<level[v1][v2]<<endl;
                    if(v1==enx&&v2==eny&&v3==enz)
                    {
                        flag=1;
                        ans=level[v1][v2][v3];
                    }
                    q.push(v1);
                    q.push(v2);
                    q.push(v3);
                    visited[v1][v2][v3]=true;
                }
            }
        }
    }
    if(flag)
        cout<<ans<<endl;
    else
        cout<<-1<<endl;
    return 0;
}

UVa 532 - Dungeon Master

#include<bits/stdc++.h>
using namespace std;
int graph[35][35][35];
int visited[35][35][35];
int level[35][35][35];
int x[6]={1,-1,0,0,0,0};
int y[6]={0,0,1,-1,0,0};
int z[6]={0,0,0,0,1,-1};
int main()
{
    int r,c,w,i,j,k;
    while(1)
    {
        cin>>w>>r>>c;
        if(w==0&&r==0&&c==0)
            break;
        int stx,sty,stz,enx,eny,enz;
        memset(graph,0,sizeof(graph));
        for(i=0;i<w;i++)
        {
            for(j=0;j<r;j++)
            {
                for(k=0;k<c;k++)
                {
                    char c;
                    cin>>c;
                    if(c=='S')
                    {
                        stx=i;
                        sty=j;
                        stz=k;
                        graph[i][j][k]=1;
                        continue;
                    }
                    if(c=='E')
                    {
                        enx=i;
                        eny=j;
                        enz=k;
                        graph[i][j][k]=1;
                    }
                    if(c=='.')
                        graph[i][j][k]=1;
                    if(c=='#')
                        graph[i][j][k]=0;
                }
            }
        }
        memset(visited,0,sizeof(visited));
        memset(level,0,sizeof(level));
        queue<int>q;
        visited[stx][sty][stz]=true;
        level[stx][sty][stz]=0;
        q.push(stx);
        q.push(sty);
        q.push(stz);
        int ans;
        bool flag=0;
        while(!q.empty())
        {
            int f1,f2,f3;
            f1=q.front();
            q.pop();
            f2=q.front();
            q.pop();
            f3=q.front();
            q.pop();
            for(int in=0;in<6;in++)
            {
                int v1,v2,v3;
                v1=f1+x[in];
                v2=f2+y[in];
                v3=f3+z[in];
                if(!visited[v1][v2][v3]&&!level[v1][v2][v3]&&graph[v1][v2][v3]==1&&(v1>=0&&v1<w&&v2>=0&&v2<r&&v3>=0&&v3<c))
                {
                    {
                        level[v1][v2][v3]=level[f1][f2][f3]+1;
                        //cout<<"LEVEL:"<<level[v1][v2]<<endl;
                        if(v1==enx&&v2==eny&&v3==enz)
                        {
                            flag=1;
                            ans=level[v1][v2][v3];
                        }
                        q.push(v1);
                        q.push(v2);
                        q.push(v3);
                        visited[v1][v2][v3]=true;
                    }
                }
            }
        }
        if(flag)
        {
            if(ans<2)
            {
                cout<<"Escaped in "<<ans<<" minute."<<endl;
            }
            else
            {
                cout<<"Escaped in "<<ans<<" minute(s)."<<endl;
            }
        }
        else
            cout<<"Trapped!"<<endl;
    }
    return 0;
}

Light OJ 1021 Painful Bases

#include<bits/stdc++.h>
#define mxn 20
using namespace std;
typedef long long ll;
ll n,arr[50],b,k;
string s;
ll dp[25][1<<17];
ll Set(ll N,ll pos){return N=N | (1<<pos);}
ll reset(ll N,ll pos){return N= N & ~(1<<pos);}
bool check(ll N,ll pos){return (bool)(N & (1<<pos));}
ll solve(ll value,ll mask)
{
    if(mask==(1<<n)-1)
    {
        if(value==0)
            return 1;
        else
            return 0;
    }
    if(dp[value][mask]!=-1)
    {
        return dp[value][mask];
    }
    ll ans=0;
    for(ll i=0;i<n;i++)
    {
        if(check(mask,i)==0)
        {
            ans+=solve((value*b+s[i])%k,Set(mask,i));
        }
    }
    return dp[value][mask]=ans;
}
int main()
{
    ll i,j,l,m,test;
    cin>>test;
    for(l=1;l<=test;l++)
    {
        cin>>b>>k;
        cin>>s;
        memset(dp,-1,sizeof(dp));
        n=s.size();
        for(i=0;i<n;i++)
        {
            if(s[i]>='0'&&s[i]<='9')
            {
                s[i]=s[i]-'0';
            }
            else
            {
                s[i]=s[i]-'A'+10;
            }
        }
        cout<<"Case "<<l<<": "<<solve(0,0)<<endl;
    }
    return 0;
}

Light OJ 1017 Brush (III)

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll arr[1009],dp[1009][1009];

ll n,l;

ll solve(ll pos,ll lft)

{

    ll i;

    if(pos>=n||lft<=0)

        return 0;

    if(dp[pos][lft]!=-1)

        return dp[pos][lft];

    ll bnd=arr[pos]+l;

    ll cnt=0;

    for(i=pos;i<n;i++)

    {

        if(arr[i]<=bnd)

        {

            cnt++;

        }

        else

        {

            break;

        }

    }

    return dp[pos][lft]=max(cnt+solve(i,lft-1),solve(pos+1,lft));

}

int main()

{

    ll i,j,k,m,test,x;

    cin>>test;

    for(k=1;k<=test;k++)

    {

        memset(dp,-1,sizeof(dp));

        cin>>n>>l>>m;

        for(i=0;i<n;i++)

        {

            cin>>x>>arr[i];

        }

        sort(arr,arr+n);

        cout<<"Case "<<k<<": "<<solve(0,m)<<endl;

    }

}