手写int128,但60分,调疯了,救救孩子
查看原帖
手写int128,但60分,调疯了,救救孩子
1158999
joeyzy楼主2024/7/3 16:36
#include<bits/stdc++.h>
using namespace std;
long long mod=1e18;

struct int128{
    long long hig;
    long long low;
    

};

int128 operator +(int128 a,int128 b)
{
    int128 k;k.hig=0;k.low=0;
    k.low=a.low+b.low;
    k.hig=k.low/mod+a.hig+b.hig;
    k.low%=mod;
    return k;
}

int128 operator -(int128 a,int128 b)
{
    int128 k;k.hig=0;k.low=0;
    k.low=a.low-b.low;
    if(k.low<0)
    {
        k.hig--;
        k.low=mod+k.low;
    }
    k.hig+=(a.hig-b.hig);
    return k;
}

int128 operator * (int128 a,long long b)
{
	int128 k;
	k.low=0,k.hig=0;
	k.low=a.low*b;
	k.hig+=(k.low/mod+b*a.hig);//与上同理
	k.low%=mod;
	return k;
}

int128 tmax(int128 a,int128 b)
{
	if(a.hig>b.hig) return a;
	if(a.hig<b.hig) return b;
	if(a.low>b.low) return a;
	if(a.low<b.low) return b;
	return a;
}

int arr[100][100];
int128 dp[100][100][100];
int128 qmi[100];

int128 into(long long a)
{
    int128 b;
    b.hig=0;
    b.low=a;
    return b;
}

void init()
{
    qmi[0]=into(1);
    for(int i=1;i<=81;i++)
    {
        qmi[i]=qmi[i-1]*(2);
    }
    return ;
}

signed main()
{
    int n,m;cin>>n>>m;
    init();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>arr[j][i];
            dp[0][m][i]=into(0);
            dp[1][m+1][i]=into(0);
        }
    }
    int128 ans;ans.hig=0;ans.low=0;
    for(int t=1;t<=n;t++)
    {
        for(int i=1;i<=m;i++)
        {
            for(int j=m;j>=i;j--)
            {
                dp[i][j][t]=tmax(dp[i-1][j][t]+qmi[m-j+i-1]*(arr[i-1][t]),dp[i][j][t]);
                dp[i][j][t]=tmax(dp[i][j+1][t]+qmi[m-j+i-1]*(arr[j+1][t]),dp[i][j][t]);
            }
        }
        int128 temp;temp.low=0;temp.hig=0;
        for(int i=1;i<=m;i++)
        {
            temp=tmax(temp,dp[i][i][t]+qmi[m]*(arr[i][t]));
        }
        ans=ans+temp;
    }
    if(ans.hig!=0)
    cout<<ans.hig<<ans.low<<endl;
    else 
    cout<<ans.low<<endl;
    return 0;
}
2024/7/3 16:36
加载中...