1 solutions
-
0
C++ :
#include<cstdio> #include<cstring> #include<algorithm> #include<climits> #include<cmath> #define rep(i,n) for(int i=1;i<=n;i++) using namespace std; const int N=200010; typedef long long ll; int v[N],w[N],l[N],r[N],n,m; ll ans,sum[N],tim[N],s; int L,R,M; ll ok(int M) { ll res=0; memset(sum,0,sizeof(sum)); memset(tim,0,sizeof(sum)); rep(i,n)if(w[i]>=M)sum[i]=v[i],tim[i]=1; rep(i,n)sum[i]+=sum[i-1],tim[i]+=tim[i-1]; rep(i,m)res+=(sum[r[i]]-sum[l[i]-1])*(tim[r[i]]-tim[l[i]-1]); return res; } int main() { scanf("%d%d%lld",&n,&m,&s); rep(i,n)scanf("%d%d",&w[i],&v[i]),R=max(R,w[i]+1); rep(i,m)scanf("%d%d",&l[i],&r[i]); ans=LLONG_MAX; while(L<R) { int M=(L+R)>>1; ll res=ok(M); if(res<=s)R=M; else L=M+1; ans=min(ans,abs(res-s)); } printf("%lld\n",ans); return 0; }Pascal :
var s,y,tmp,ans:int64; mid,left,right,i,n,m,max,min:longint; c,a,w,v,l,r:array[0..200001]of longint; procedure work(t:longint); var i:longint; count,tot:int64; begin fillchar(a,sizeof(a),0); fillchar(c,sizeof(c),0); for i:=1 to n do begin if w[i]>=t then begin a[i]:=a[i-1]+v[i]; c[i]:=c[i-1]+1; end else begin a[i]:=a[i-1]; c[i]:=c[i-1]; end; end; y:=0; for i:=1 to m do begin count:=c[r[i]]-c[l[i]-1]; tot:=a[r[i]]-a[l[i]-1]; y:=y+count*tot; end; end; begin read(n,m,s); max:=0; min:=maxlongint-1; for i:=1 to n do begin read(w[i],v[i]); if w[i]>max then max:=w[i]; if w[i]<min then min:=w[i]; end; for i:=1 to m do begin read(l[i],r[i]); end; left:=min-1;right:=max+1; ans:=maxlongint*100000; while left<right do begin mid:=(left+right) div 2; work(mid); tmp:=s-y; if abs(tmp)<ans then ans:=abs(tmp); if ans=0 then break; if s>y then right:=mid else left:=mid+1; end; writeln(ans); end.
- 1
Information
- ID
- 19978
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- (None)
- Tags
- # Submissions
- 0
- Accepted
- 0
- Uploaded By