제출 #245132

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
245132		A02	쌀 창고 (IOI11_ricehub)	C++14	49 / 100	31 ms	1792 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)
{

    int left_best = 0;
    int right_best = 0;
    long long current_cost = 0;
    int current_field = 0;
    int 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++;
    }

    int best = current_max;

    while (current_field != R - 1){

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

        int to_right = right_best - current_field;
        int 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){
            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: 0 / 25
• Subtask 3: 0 / 26
• Subtask 4: 32 / 32