Cod sursa(job #2012199)

Utilizator Mircea_DonciuDonciu Mircea Mircea_Donciu Data 18 august 2017 11:45:48
Problema Peste Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.91 kb
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <memory>

const int kMaxDim = 50005;
const int kMaxTime = 1005;

class Reader {
    public:
        Reader(const std::string& filename) :
            m_stream(filename),
            m_pos(kBufferSize - 1),
            m_buffer(new char[kBufferSize]) {
            Next();
        }

        template<typename T>
        Reader& operator>>(T& value) {
            value = 0;
            while (Current() < '0' || Current() > '9')
                Next();
            while (Current() >= '0' && Current() <= '9') {
                value = value * 10 + Current() - '0';
                Next();
            }
            return *this;
        }

    private:
        const int kBufferSize = (1 << 18);

        char Current() {
            return m_buffer[m_pos];
        }

        void Next() {
            if (!(++m_pos != kBufferSize)) {
                m_stream.read(m_buffer.get(), kBufferSize);
                m_pos = 0;
            }
        }

        std::ifstream m_stream;
        int m_pos;
        std::unique_ptr<char[]> m_buffer;
};

struct Net {
    bool operator < (const Net& obj) const {
        return this->time < obj.time;
    }

    short int fish, time;
};

int netCount, maximumNets, totalTime;
int precalcMaximumFishCount[kMaxTime];
unsigned short int fr[kMaxTime];
short int f[kMaxDim], t[kMaxDim];
long long dp[kMaxDim];
Net nets[kMaxDim];

std::priority_queue< int > heap;

int main() {
    Reader inputFile("peste.in");
    std::ofstream outputFile("peste.out");

    inputFile >> netCount >> maximumNets >> totalTime;
    for (int i = 0; i < netCount; i++)
        inputFile >> nets[i].fish >> nets[i].time;

    for (int i = 0; i < netCount; i++)
        fr[nets[i].time]++;
    for (int i = 1; i < kMaxTime; i++)
        fr[i] += fr[i - 1];
    for (int i = 0; i < netCount; i++) {
        int temp = -1 + fr[nets[i].time]--;
        f[temp] = nets[i].fish;
        t[temp] = nets[i].time;
    }

    for (int i = 0, sum = 0; i < netCount; i++) {
        heap.push(-f[i]);
        sum += f[i];

        if (i >= maximumNets) {
            sum += heap.top();
            heap.pop();
        }

        precalcMaximumFishCount[t[i]] = sum;
    }

    int maxTime = t[netCount - 1];
    for (int i = 1; i <= maxTime; i++)
        precalcMaximumFishCount[i] = std::max(precalcMaximumFishCount[i], precalcMaximumFishCount[i - 1]);

    for (int i = 1; i <= maxTime; i++)
        for (int j = 1; j <= i; j++)
            dp[i] = std::max(dp[i], dp[i - j] + precalcMaximumFishCount[j]);
    for (int i = maxTime + 1; i <= totalTime; i++)
        for (int j = 1; j <= maxTime; j++)
            dp[i] = std::max(dp[i], dp[i - j] + precalcMaximumFishCount[j]);

    outputFile << dp[totalTime] << '\n';

    outputFile.close();

    return 0;
}