Pagini recente » Cod sursa (job #2963176) | Cod sursa (job #2770959) | Cod sursa (job #2218290) | Cod sursa (job #1352734) | Cod sursa (job #1127118)
#include <fstream>
#include <vector>
#include <deque>
using namespace std;
vector<int> nr;
deque<int> deQueue;
void readData(int &, int &);
void solve(int, int, long long &);
void writeData(long long);
int main(int argc, char *argv[]) {
int totalSize, subseqSize;
long long sum;
readData(totalSize, subseqSize);
solve(totalSize, subseqSize, sum);
writeData(sum);
return 0;
}
void readData(int &totalSize, int &subseqSize) {
fstream in("deque.in", ios::in);
in >> totalSize >> subseqSize;
nr.resize(totalSize);
for (int i = 1; i <= totalSize; ++i) {
nr.push_back(i);
}
in.close();
}
void solve(int totalSize, int subseqSize, long long &sum) {
for (vector<int>::iterator it = nr.begin(); it != nr.end(); ++it) {
while (!deQueue.empty() && (*it) < deQueue.back()) {
deQueue.pop_back();
}
deQueue.push_back(*it);
if (deQueue.front() == (*it) - subseqSize) {
deQueue.pop_front();
}
if ((*it) >= subseqSize) {
sum += deQueue.front();
}
}
}
void writeData(long long sum) {
fstream out("deque.out", ios::out);
out << sum;
out.close();
}