Codeforces Round #547 (Div. 3)F1. Same Sum Blocks (Easy)
Codeforces Round #547 (Div. 3)F1. Same Sum Blocks (Easy)
glm233
发布于 2020-09-28 10:39:42
发布于 2020-09-28 10:39:42
F1. Same Sum Blocks (Easy)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
This problem is given in two editions, which differ exclusively in the constraints on the number nn.
You are given an array of integers a[1],a[2],…,a[n].a[1],a[2],…,a[n]. A block is a sequence of contiguous (consecutive) elements a[l],a[l+1],…,a[r]a[l],a[l+1],…,a[r] (1≤l≤r≤n1≤l≤r≤n). Thus, a block is defined by a pair of indices (l,r)(l,r).
Find a set of blocks (l1,r1),(l2,r2),…,(lk,rk)(l1,r1),(l2,r2),…,(lk,rk) such that:
- They do not intersect (i.e. they are disjoint). Formally, for each pair of blocks (li,ri)(li,ri) and (lj,rj(lj,rj) where i≠ji≠j either ri<ljri<lj or rj<lirj<li.
- For each block the sum of its elements is the same. Formally, a[l1]+a[l1+1]+⋯+a[r1]=a[l2]+a[l2+1]+⋯+a[r2]=a[l1]+a[l1+1]+⋯+a[r1]=a[l2]+a[l2+1]+⋯+a[r2]= ⋯=⋯= a[lk]+a[lk+1]+⋯+a[rk].a[lk]+a[lk+1]+⋯+a[rk].
- The number of the blocks in the set is maximum. Formally, there does not exist a set of blocks (l′1,r′1),(l′2,r′2),…,(l′k′,r′k′)(l1′,r1′),(l2′,r2′),…,(lk′′,rk′′)satisfying the above two requirements with k′>kk′>k.
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#include<unordered_set>
#define rg register ll
#define inf 2147483647
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define ll long long
#define maxn 200005
const double eps = 1e-8;
using namespace std;
inline ll read()
{
char ch = getchar(); ll s = 0, w = 1;
while (ch < 48 || ch>57) { if (ch == '-')w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
return s * w;
}
inline void write(ll x)
{
if (x < 0)putchar('-'), x = -x;
if (x > 9)write(x / 10);
putchar(x % 10 + 48);
}
inline bool cmp(const pair<ll,ll>&a,const pair<ll,ll>&b)
{
return a.second<b.second;
}
int main()
{
ll n=read();
vector<ll>a(n+5);
map<ll,vector<pair<ll,ll>>>p;
for(rg i=1;i<=n;i++)a[i]=read();
for(rg i=1;i<=n;i++)
{
ll sum=0;
for(rg j=i;j<=n;j++)
{
sum+=a[j];
p[sum].push_back(make_pair(i,j));
}
}
ll ans=0;
vector<pair<ll,ll>>res;
for(const auto& it:p)
{
vector<pair<ll,ll>>now=it.second;
sort(now.begin(),now.end(),cmp);
vector<pair<ll,ll>>temp;
ll cur=0,r=-1;
for(const auto &itt:now)
{
if(itt.first>r)
{
cur++;
temp.push_back(itt);
r=itt.second;
}
}
if(cur>ans)
{
ans=cur;
res=temp;
}
}
cout<<ans<<endl;
for(auto it:res)
{
cout<<it.first<<" "<<it.second<<endl;
}
return 0;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019/08/09 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
