2 条题解

  • 0
    @ 2025-10-8 16:57:55
    #include <bits/stdc++.h>
    using namespace std;
    
    using ll=long long;
    const ll inf=0x3f3f3f3f3f3f3f3f;
    const int N=705;
    ll a[N][N];
    int main()
    {
    	ios::sync_with_stdio(0);cin.tie(0);
    	int n,K;cin>>n>>K;
        memset(a,0,sizeof(a));
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=i;j++)
    		{
    			cin>>a[i][j];
    			a[i][j]+=a[i][j-1];
    		}
    	}
    	ll ans=-inf;
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=i;j++)
    		{
    			ll sum=0;
    			for(int k=1;k<=n-i+1;k++)
    			{
    				sum+=a[i+k-1][j+k-1]-a[i+k-1][j-1];
    				if(k<K)continue;
    				if(k>K*2)break;
    				ans=max(ans,sum/(k*(k+1)/2));
    			}
    		}
    	}
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=i;j++)
    		{
    			ll sum=0;
    			for(int k=1;k<=j&&k<=i-j+1;k++)
    			{
    				sum+=a[i-k+1][j]-a[i-k+1][j-k];
    				if(k<K)continue;
    				if(k>K*2)break;
    				ans=max(ans,sum/(k*(k+1)/2));
    			}
    		}
    	}
    	cout<<ans<<'\n';
    	return 0;
    }
    
    • 0
      @ 2025-10-8 16:57:48
      #include <bits/stdc++.h>
      using namespace std;
      
      using ll=long long;
      const ll inf=0x3f3f3f3f3f3f3f3f;
      const int N=705;
      ll a[N][N];
      int main()
      {
      	ios::sync_with_stdio(0);cin.tie(0);
      	int n,K;cin>>n>>K;
          memset(a,0,sizeof(a));
      	for(int i=1;i<=n;i++)
      	{
      		for(int j=1;j<=i;j++)
      		{
      			cin>>a[i][j];
      			a[i][j]+=a[i][j-1];
      		}
      	}
      	ll ans=-inf;
      	for(int i=1;i<=n;i++)
      	{
      		for(int j=1;j<=i;j++)
      		{
      			ll sum=0;
      			for(int k=1;k<=n-i+1;k++)
      			{
      				sum+=a[i+k-1][j+k-1]-a[i+k-1][j-1];
      				if(k<K)continue;
      				if(k>K*2)break;
      				ans=max(ans,sum/(k*(k+1)/2));
      			}
      		}
      	}
      	for(int i=1;i<=n;i++)
      	{
      		for(int j=1;j<=i;j++)
      		{
      			ll sum=0;
      			for(int k=1;k<=j&&k<=i-j+1;k++)
      			{
      				sum+=a[i-k+1][j]-a[i-k+1][j-k];
      				if(k<K)continue;
      				if(k>K*2)break;
      				ans=max(ans,sum/(k*(k+1)/2));
      			}
      		}
      	}
      	cout<<ans<<'\n';
      	return 0;
      }
      • 1

      【模拟+优化】等边三角形平均值最大[USACO11FEB] The Triangle S

      信息

      ID
      1561
      时间
      1000ms
      内存
      128MiB
      难度
      6
      标签
      递交数
      122
      已通过
      37
      上传者