Pagini recente » Cod sursa (job #3263079) | Cod sursa (job #1071796) | Cod sursa (job #2800833) | Cod sursa (job #3216844) | Cod sursa (job #2730767)
#include <cstddef>
#include <vector>
#include <fstream>
template<typename T>
class Deque
{
public:
Deque() = default;
Deque(const std::size_t count, const T& value)
: capacity(count)
{
data = new T[count];
for(std::size_t i = 0; i < count; ++i)
{
data[i] = value;
}
endidx = count;
}
~Deque()
{
if(data != nullptr)
{
delete[] data;
}
}
void push_back(const T& value)
{
if(data != nullptr)
{
if(endidx == capacity)
{
extend_right(capacity * 2);
}
data[endidx] = value;
++endidx;
}
else
{
data = new T[1];
*data = value;
capacity = 1;
endidx = 1;
}
}
void push_front(const T& value)
{
if(data != nullptr)
{
if(begidx == 0)
{
extend_left(size(), size() * 2);
}
--begidx;
data[begidx] = value;
}
else
{
data = new T[1];
*data = value;
capacity = 1;
endidx = 1;
}
}
void pop_back()
{
--endidx;
}
void pop_front()
{
++begidx;
}
T& front()
{
return data[begidx];
}
T& back()
{
return data[endidx - 1];
}
const T& front() const
{
return data[begidx];
}
const T& back() const
{
return data[endidx - 1];
}
T* begin()
{
return (data + begidx);
}
T* end()
{
return (data + endidx);
}
const T* begin() const
{
return (data + begidx);
}
const T* end() const
{
return (data + endidx);
}
std::size_t size() const
{
if(data != nullptr)
{
return endidx - begidx;
}
return 0;
}
bool empty() const
{
return (data == nullptr || begidx == endidx);
}
private:
void extend_left(const std::size_t currentsize, const std::size_t newsize)
{
T* newdata = new T[newsize];
const std::size_t difference = newsize - currentsize;
for(std::size_t i = begidx + difference; i < endidx + difference; ++i)
{
newdata[i] = data[i - difference];
}
delete[] data;
data = newdata;
begidx += difference;
endidx += difference;
capacity = newsize;
}
void extend_right(const std::size_t newsize)
{
T* newdata = new T[newsize];
for(std::size_t i = begidx; i < endidx; ++i)
{
newdata[i] = data[i];
}
delete[] data;
data = newdata;
capacity = newsize;
}
private:
T* data = nullptr;
std::size_t begidx = 0;
std::size_t endidx = 0;
std::size_t capacity = 0;
};
int main()
{
std::ifstream fin("branza.in");
std::ofstream fout("branza.out");
unsigned N;
unsigned S;
unsigned T;
fin >> N >> S >> T;
std::vector<std::pair<unsigned, unsigned>> vec;
for(std::size_t i = 0; i < N; ++i)
{
unsigned v1;
unsigned v2;
fin >> v1 >> v2;
vec.push_back(std::make_pair(v1, v2));
}
Deque<unsigned> deq;
unsigned suma = 0;
for(unsigned i = 0; i < N; ++i)
{
while(!deq.empty() && vec[i].first <= vec[deq.back()].first + S * (i - deq.back()))
{
deq.pop_back();
}
deq.push_back(i);
if(i - deq.front() == T)
{
deq.pop_front();
}
const unsigned d_idx = deq.front();
suma += vec[i].second * (vec[d_idx].first + S * (i - d_idx));
}
fout << suma << '\n';
}