oj.uz

Submission #229567

# Submission time Handle Problem Language Result Execution time Memory
229567 2020-05-05T07:28:07 Z monus1042 Rice Hub (IOI11_ricehub) C++17
17 / 100
 20 ms 1664 KB 
#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;
#define ll long long

int besthub(int R, int L, int X[], long long B)	{
	int ans=1;
	ll cost=0;

	int l=0,r=0;
	for (int i=1; i<R; i++){
		if (cost + (ll)(X[i] - X[0]) <= B){
			ans++;
			cost += (ll)(X[i] - X[0]);
			r++;
		}else break;
	}
	int forward[R], backward[R];
	for (int i=0; i<R; i++){
		int curr=X[i];
		int j, cnt=1;
		for (j=i; j<R && X[j] == curr; j++){
			forward[j]=cnt;
			cnt++;
		}
		j--;
		for (int k=j, c=1; k>=i; k--, c++){
			backward[k]=c;
		}
		i=j;
	}

	for (int i=1; i<R; i++){
		ll dist=X[i] - X[i-1];
		if (r<i){
			r=i;
		}else{
			cost -= dist * (ll)(r-(i-1));
		}
		cost += dist * (ll)(i-l - forward[i-1] + 1) * forward[i-1];
		if (cost == B) {}
		else if (cost < B){
			while(1){
				if (r+1 < R && cost + (ll)(X[r+1] - X[i]) <= B){
					cost += (ll)(X[r+1] - X[i]);
					r++;
				}else break;
			}
		}else{ // cost > B
			while(1){
				if (cost <= B) break;
				cost -= (ll)(X[i] - X[l]);
				l++;
			}
			//try to expand
			while(1){
				if (r+1 < R && cost + (ll)(X[r+1] - X[i]) <= B){
					cost += (ll)(X[r+1] - X[i]);
					r++;
				}else break;
			}
		}
		ans=max(ans, r-l+1);
	}

	return ans;
}

Compilation message

ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:18:18: warning: variable 'backward' set but not used [-Wunused-but-set-variable]
  int forward[R], backward[R];
                  ^~~~~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 256 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 5 ms 256 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 4 ms 256 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 4 ms 256 KB Output is correct
11 Correct 4 ms 256 KB Output is correct
12 Correct 4 ms 256 KB Output is correct
13 Incorrect 5 ms 256 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Incorrect 5 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 7 ms 640 KB Output is correct
2 Correct 7 ms 512 KB Output is correct
3 Correct 20 ms 1528 KB Output is correct
4 Correct 20 ms 1536 KB Output is correct
5 Runtime error 13 ms 1664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -