답안 #26968 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
26968	2017-07-07T16:00:41 Z	repeating	쌀 창고 (IOI11_ricehub)	C++11	100 / 100	103 ms	15692 KB

ricehub

#include <bits/stdc++.h>
#include "ricehub.h"
#define F first
#define S second
#define P push
#define pb push_back
#define MEM(dp,i) memset(dp,i,sizeof(dp))
#define W while
#define R return
#define C continue
#define SI size()
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define pii pair<int,int>
#define SF(x) scanf("%I64d",&x)
#define SF2(x,y) scanf("%I64d%I64d",&x,&y)
#define SF3(x,y,z) scanf("%I64d%I64d%I64d",&x,&y,&z)
#define SF4(x,y,z,o) scanf("%I64d%I64d%I64d%I64d",&x,&y,&z,&o)
#define all(v) v.begin(),v.end()
#define MAX_R  1000000

using namespace std;
const long long INF = 1e9+5e8;
const int MX=100009;
int a[MX];
ll n,b;
ll seg[MX*4];
ll f[MX*8];
void u(int node,int l,int r,int s,int e,int val){
    if(r<s||e<l)R;
    seg[node]+=f[node]*(r-l+1);
    f[node*2]+=f[node];
    f[node*2+1]+=f[node];
    f[node]=0;
    if(s<=l&&r<=e){
        seg[node]+=val*(r-l+1);
        f[node*2]+=val;
        f[node*2+1]+=val;
        R;
    }
    u(node*2,l,(l+r)/2,s,e,val);
    u(node*2+1,(l+r)/2+1,r,s,e,val);
    seg[node]=seg[node*2]+seg[node*2+1];
}
ll q(int node,int l,int r,int s,int e){
    if(r<s||e<l)R 0;
    seg[node]+=f[node]*(r-l+1);
    f[node*2]+=f[node];
    f[node*2+1]+=f[node];
    f[node]=0;
    if(s<=l&&r<=e)R seg[node];
    ll ret=0;
    ret+=q(node*2,l,(l+r)/2,s,e);
    ret+=q(node*2+1,(l+r)/2+1,r,s,e);
    R ret;
}
void change(int p1,int &p,int p2){
    int mid=(p1+p2)/2;
    if(mid==p)R;
    u(1,0,n-1,0,p,a[p+1]-a[p]);
    u(1,0,n-1,p+1,n-1,a[p]-a[p+1]);
    p++;
}
int solve(){
    for(int i=0;i<n;i++){
        u(1,0,n-1,i,i,a[i]-a[0]);
    }
    int ret=1;
    int p1=0,p2=0,p=0;
    W(p2<n){
        W(q(1,0,n-1,p1,p2)>b){
//            cout<<p1<<" "<<p2<<" "<<q(1,0,n-1,p1,p2)<<endl;
            p1++;
            change(p1,p,p2);
        }
//        cout<<p1<<" "<<p2<<endl;
        ret=max(ret,p2-p1+1);
        p2++;
        change(p1,p,p2);
    }
    R ret;
}
int besthub(int r, int L, int X[], long long B)
{
    n=r;
    b=B;
    for(int i=0;i<n;i++){
        a[i]=X[i];
    }
    return solve();
}

//static int r, L;
//static long long B;
//static int X[MAX_R];
//static int solution;
//
//inline
//void my_assert(int e) {if (!e) abort();}
//
//static void read_input()
//{
//  int i;
//  my_assert(3==scanf("%d %d %lld",&r,&L,&B));
//  for(i=0; i<r; i++)
//    my_assert(1==scanf("%d",&X[i]));
//  my_assert(1==scanf("%d",&solution));
//}
//
//int main()
//{
//  int ans;
//  read_input();
//  ans = besthub(r,L,X,B);
//  if(ans==solution)
//    printf("Correct.\n");
//  else
//    printf("Incorrect.  Returned %d instead of %d.\n",ans,solution);
//
//  return 0;
//}
//

Subtask #1
17.0 / 17.0

#	결과	메모리	Grader output
1	Correct	15692 KB	Output is correct
2	Correct	15692 KB	Output is correct
3	Correct	15692 KB	Output is correct
4	Correct	15692 KB	Output is correct
5	Correct	15692 KB	Output is correct

Subtask #2
25.0 / 25.0

#	결과	메모리	Grader output
1	Correct	15692 KB	Output is correct
2	Correct	15692 KB	Output is correct
3	Correct	15692 KB	Output is correct
4	Correct	15692 KB	Output is correct
5	Correct	15692 KB	Output is correct
6	Correct	15692 KB	Output is correct
7	Correct	15692 KB	Output is correct
8	Correct	15692 KB	Output is correct
9	Correct	15692 KB	Output is correct
10	Correct	15692 KB	Output is correct
11	Correct	15692 KB	Output is correct
12	Correct	15692 KB	Output is correct
13	Correct	15692 KB	Output is correct
14	Correct	15692 KB	Output is correct
15	Correct	15692 KB	Output is correct
16	Correct	15692 KB	Output is correct
17	Correct	15692 KB	Output is correct
18	Correct	15692 KB	Output is correct
19	Correct	15692 KB	Output is correct
20	Correct	15692 KB	Output is correct
21	Correct	15692 KB	Output is correct
22	Correct	15692 KB	Output is correct
23	Correct	15692 KB	Output is correct
24	Correct	15692 KB	Output is correct
25	Correct	15692 KB	Output is correct
26	Correct	15692 KB	Output is correct
27	Correct	15692 KB	Output is correct
28	Correct	15692 KB	Output is correct

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	15692 KB	Output is correct
2	Correct	0 ms	15692 KB	Output is correct
3	Correct	0 ms	15692 KB	Output is correct
4	Correct	0 ms	15692 KB	Output is correct
5	Correct	0 ms	15692 KB	Output is correct
6	Correct	0 ms	15692 KB	Output is correct
7	Correct	0 ms	15692 KB	Output is correct
8	Correct	0 ms	15692 KB	Output is correct
9	Correct	0 ms	15692 KB	Output is correct
10	Correct	0 ms	15692 KB	Output is correct
11	Correct	0 ms	15692 KB	Output is correct
12	Correct	0 ms	15692 KB	Output is correct
13	Correct	0 ms	15692 KB	Output is correct
14	Correct	0 ms	15692 KB	Output is correct
15	Correct	0 ms	15692 KB	Output is correct
16	Correct	0 ms	15692 KB	Output is correct
17	Correct	0 ms	15692 KB	Output is correct
18	Correct	0 ms	15692 KB	Output is correct
19	Correct	0 ms	15692 KB	Output is correct
20	Correct	0 ms	15692 KB	Output is correct
21	Correct	6 ms	15692 KB	Output is correct
22	Correct	6 ms	15692 KB	Output is correct
23	Correct	3 ms	15692 KB	Output is correct
24	Correct	3 ms	15692 KB	Output is correct
25	Correct	3 ms	15692 KB	Output is correct
26	Correct	3 ms	15692 KB	Output is correct
27	Correct	3 ms	15692 KB	Output is correct
28	Correct	6 ms	15692 KB	Output is correct

Subtask #4
32.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	15692 KB	Output is correct
2	Correct	26 ms	15692 KB	Output is correct
3	Correct	79 ms	15692 KB	Output is correct
4	Correct	76 ms	15692 KB	Output is correct
5	Correct	66 ms	15692 KB	Output is correct
6	Correct	69 ms	15692 KB	Output is correct
7	Correct	89 ms	15692 KB	Output is correct
8	Correct	103 ms	15692 KB	Output is correct
9	Correct	76 ms	15692 KB	Output is correct
10	Correct	79 ms	15692 KB	Output is correct
11	Correct	99 ms	15692 KB	Output is correct
12	Correct	89 ms	15692 KB	Output is correct
13	Correct	69 ms	15692 KB	Output is correct
14	Correct	69 ms	15692 KB	Output is correct
15	Correct	69 ms	15692 KB	Output is correct
16	Correct	66 ms	15692 KB	Output is correct
17	Correct	89 ms	15692 KB	Output is correct
18	Correct	83 ms	15692 KB	Output is correct
19	Correct	79 ms	15692 KB	Output is correct
20	Correct	79 ms	15692 KB	Output is correct

답안 #26968

Compilation message

Subtask #1 17.0 / 17.0

Subtask #2 25.0 / 25.0

Subtask #3 26.0 / 26.0

Subtask #4 32.0 / 32.0

Subtask #1
17.0 / 17.0

Subtask #2
25.0 / 25.0

Subtask #3
26.0 / 26.0

Subtask #4
32.0 / 32.0