oj.uz

Submission #261550

# Submission time Handle Problem Language Result Execution time Memory
261550 2020-08-11T21:01:38 Z oscarsierra12 Rice Hub (IOI11_ricehub) C++14
17 / 100
 209 ms 2680 KB 
#include "ricehub.h"
#include <stdio.h>
#include <stdlib.h>
#include <iostream>

using namespace std ;

const int N = 2e5 ;

long long ac[N], ac2[N] ;

int besthub(int R, int L, int X[], long long B)
{
  for ( int i = 1 ; i < R ; ++i ) ac[i] = ac[i-1] + 1ll * (X[i] - X[i-1]) * i;
  for ( int i = R-2 ; i >= 0 ; --i ) ac2[i] = ac2[i+1] + 1ll * (X[i+1] - X[i]) * (R-i-1) ;
  int ans = 0 ;
  for ( int i = 0 ; i < R ; ++i ) {
    int lw = i, hg = R-1 ;
    while ( lw <= hg ) {
        int mid = (lw + hg) >> 1 ;
        int lw2 = i, hg2 = mid ;
        int mid2 ;
        long long cost ;
        while ( lw2 < hg2 ) {
            mid2 = (lw2 + hg2) >> 1 ;
            cost = ac[mid2] - 1ll * i * (X[mid2] - X[i]) - ac[i] + ac2[mid2] - 1ll * (R-mid-1) * (X[mid] - X[mid2]) - ac2[mid];
            mid2++ ;
            long long cost2 = ac[mid2] - 1ll * i * (X[mid2] - X[i]) - ac[i] + ac2[mid2] - 1ll * (R-mid-1) * (X[mid] - X[mid2]) - ac2[mid];
            if ( cost > cost2 ) lw2 = mid2 ;
            else hg2 = mid2-1 ;
        }
        mid2 = lw2 ;
        cost = ac[mid2] - 1ll * i * (X[mid2] - X[i]) - ac[i] + ac2[mid2] - 1ll * (R-mid-1) * (X[mid] - X[mid2]) - ac2[mid];
       // cout << i << " " << mid2 << " " <<mid << " cost " << cost << " = " << ac[mid2] - 1ll * i * (X[mid2] - X[i]) - ac[i]  << " + " << ac[mid] - 1ll * mid2 * (X[mid] - X[mid2]) - ac[mid2] << endl ;
        if ( cost <= B ) lw = mid+1 ;
        else hg = mid-1 ;
    }
   // cout << i << " " << hg << endl ;
    ans = max ( ans, hg - i + 1 ) ;
  }
  return ans;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Incorrect 1 ms 384 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Incorrect 1 ms 384 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 768 KB Output is correct
2 Correct 16 ms 896 KB Output is correct
3 Correct 152 ms 2552 KB Output is correct
4 Correct 152 ms 2552 KB Output is correct
5 Correct 44 ms 1536 KB Output is correct
6 Correct 45 ms 1664 KB Output is correct
7 Correct 174 ms 2680 KB Output is correct
8 Incorrect 209 ms 2680 KB Output isn't correct
9 Halted 0 ms 0 KB -