• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

codeforces1060C

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

https://codeforces.com/contest/1060/problem/C

题意:给你一个长度为n的数列a和长度为m的数列b,定义c(i,j)=ai*bj,得到c矩阵,给定值x,求c矩阵中的子矩阵和小于等于x的最大的元素个数

题解:和hihocoder上面一题很想~链接http://hihocoder.com/problemset/problem/1502 ,不同的是这题用n^3的做法会T哭

   我们可以想到,一个子矩阵的和就是 (a[i]+a[i+1]+...+a[j])*(b[i]+b[i+1]+...+b[j])。于是我们先预处理a和b 的前缀和,然后n^2判断即可

代码如下:

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <bitset>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
#define PI acos(-1)
#define eps 1e-8
#define fuck(x) cout<<#x<<" = "<<x<<endl;
#define FIN freopen("input.txt","r",stdin);
#define FOUT freopen("output.txt","w+",stdout);
//#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int maxn = 1e5+5;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9+7;
LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
double dpow(double a,LL b){double ans=1.0;while(b){if(b%2)ans=ans*a;a=a*a;b/=2;}return ans;}
LL a[2005],b[2005],c[2005][2005];
LL sum[2005][2005];
LL suma[2005];
LL sumb[2005];
int main(){
#ifndef ONLINE_JUDGE
    FIN
#endif
    LL n,m,x; 
    cin>>n>>m;
    a[0]=b[0]=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]=a[i]+a[i-1];
    }
    for(int i=1;i<=m;i++){
        cin>>b[i];
        b[i]=b[i]+b[i-1];
    }
    cin>>x;
        memset(suma,INF,sizeof(suma));
        memset(sumb,INF,sizeof(sumb));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(j+i-1>n) break;
                suma[i]=min(suma[i],a[j+i-1]-a[j-1]);
            }
        }
        for(int i=1;i<=m;i++){
            for(int j=1;j<=m;j++){
                if(j+i-1>m) break;
                sumb[i]=min(sumb[i],b[j+i-1]-b[j-1]);
            }
        }
        LL ans=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if((LL)suma[i]*sumb[j]<=x){
                    ans=max(ans,i*j*1LL);
                }
            }
        }

        cout<<ans<<endl;
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=m;j++){
    //         cout<<c[i][j]<<" ";
    //     }
    //     cout<<endl;
    // }
}
View Code

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C#静态方法和实例方法的内存分配测试发布时间:2022-07-14
下一篇:
C语言中输入输出重定向,freopen的用法和实例发布时间:2022-07-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap