C++(clang++11) 解法, 执行用时: 494ms, 内存消耗: 24748K, 提交时间: 2021-03-19 18:40:51

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000005;
#define ll long long
ll a[maxn];
vector<pair<ll,ll>>book;
map<ll,ll>Q;
int main()
{
    int n;
    ll k;
    while(~scanf("%d%lld" , &n , &k)){
            Q.clear();
            book.clear();
            ll minn = 1e18;
            for (int i = 1 ; i <= n ; i++)
                scanf("%lld" , &a[i]) , minn = min(minn , a[i]);
            if (minn > k) {
                printf("No!\n");
                continue;
            }
            ll now = 0 , ans = -1e18;
            Q[0] = 1;
            book.push_back(make_pair(-1e18 , 0));
            for (int i = 1 ; i <= n ; i++){
                now += a[i];
                auto g = Q.lower_bound(now - k);
                if (g != Q.end()){
                  ans = max(ans , now - g->first);
                  book.push_back(make_pair(now - g->first , g->second));
                }
                else book.push_back(make_pair(-1e18 , 0));
                Q[now]++;
            }
            ll cnt = 0;
            for (int i = 1 ; i <= n ; i++){
                if (book[i].first == ans){
                    cnt += book[i].second;
                }
            }
            printf("%lld\n" , ans);
            printf("%lld\n" , cnt);
        }
    return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 595ms, 内存消耗: 16236K, 提交时间: 2023-03-30 20:14:46

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int a[N],s[N];
int n,m;
unordered_map<int,int> mp; set<int> se;
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    while(cin>>n>>m)
    {
        mp.clear();
        se.clear();
        int mini=1e18;
        for(int i=1;i<=n;i++)cin>>a[i],mini=min(mini,a[i]);
        for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
//         if(mini>m)cout<<"No!\n";
//         else
//         {
            int ans=-1e18,tmp=0;
            for(int i=n;i>=1;i--)
            {
                se.insert(s[i]);
                mp[s[i]]++;
                if(*se.begin()>s[i-1]+m);
                else 
                {
                    auto it=se.upper_bound(s[i-1]+m);
                    it--;
//                     if(*it>=s[i-1])
//                     {
                        if(*it-s[i-1]>ans)
                        {
                            ans=*it-s[i-1];
                            tmp=mp[*it];
                        }
                        else if(*it-s[i-1]==ans)tmp+=mp[*it];
//                     }
                }
            }
        if(tmp==0)cout<<"No!\n";
        else cout<<ans<<'\n'<<tmp<<'\n';
//         }
    }
}

C++14(g++5.4) 解法, 执行用时: 835ms, 内存消耗: 18400K, 提交时间: 2020-06-14 20:22:59

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f3f3f3f3f;
inline ll read()
{
	ll x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
	return w==1?x:-x;
}

const int N=1e6+10;
int n;
ll a[N],mx;
int main()
{
    while(cin>>n>>mx)
    {
       for(int i=1;i<=n;++i) a[i]=read();
        ll sum=0;
        set<ll>st;
        map<ll,int>mp;
        ll ans=-inf,ans1=0;
        st.insert(0);


        for(int i=1;i<=n;++i)
        {
            sum+=a[i];
            auto it=st.lower_bound(sum-mx);
            if(it!=st.end()){
                ll tmp=sum-(*it);
                ans=max(ans,tmp);
            }
            st.insert(sum);
        }
        if(ans==-inf) {
            puts("No!");
            continue;
        }

        mp[0]++,sum=0;
        for(int i=1;i<=n;++i){
            sum+=a[i];
            ans1+=mp[sum-ans];
            mp[sum]++;
        }

        printf("%lld\n%lld\n",ans,ans1);
    }
}