Submission #245142

#	Time	Username	Problem	Language	Result	Execution time	Memory
245142		A02	Rice Hub (IOI11_ricehub)	C++11	100 / 100	24 ms	768 KiB

ricehub

#include "ricehub.h"
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <iostream>
#include <fstream>

using namespace std;
int besthub(int R, int L, int X[], long long B)
{

    long long left_best = 0;
    long long right_best = 0;
    long long current_cost = 0;
    long long current_field = 0;
    long long current_max = 1;

    while (current_cost <= B){

        if (right_best == R - 1){
            break;
        }

        if (X[right_best + 1] - X[0] + current_cost > B){
            break;
        }

        right_best++;
        current_cost += X[right_best] - X[0];
        current_max++;
    }

    long long best = current_max;

    while (current_field != R - 1){

        long long distance_moved = X[current_field + 1] - X[current_field];

        long long to_right = right_best - current_field;
        long long to_left =  current_field - left_best + 1;

        current_cost += to_left * distance_moved;
        current_cost -= to_right * distance_moved;

        if (current_field == right_best){
            right_best++;
            current_max++;
        }
        current_field++;

        while (current_cost < B && left_best != 0){
            current_cost += (X[current_field] - X[left_best - 1]);
            current_max++;
            left_best--;
        }
        while (current_cost > B){
            current_cost -= (X[current_field] - X[left_best]);
            current_max--;
            left_best++;
        }


        while (right_best != R - 1){

            if (current_cost + X[right_best + 1] - X[current_field] <= B){
                current_cost += (X[right_best + 1] - X[current_field]);
                right_best++;
                current_max++;
            } else {
                if (X[current_field] - X[left_best] > X[right_best] - X[current_field]){
                    current_cost -= (X[current_field] - X[left_best]);
                    current_cost += (X[right_best + 1] - X[current_field]);
                    right_best++;
                    left_best++;
                }  else {
                break;
            }
            }

        }

        best = max(current_max, best);
    }

    //cout << X[0] << ' ' << X[1] << ' ' << X[2] << endl;
    //cout << best << ' ' << current_cost << ' ' << right_best << ' ' << B <<  endl;
    return best;
}

• Subtask 1: 17 / 17
• Subtask 2: 25 / 25
• Subtask 3: 26 / 26
• Subtask 4: 32 / 32