Pagini recente » Profil StarGold2 | Cod sursa (job #1796193) | Cod sursa (job #52225) | Cod sursa (job #2039018) | Cod sursa (job #2894749)
/// [A][M][C][B][N] ///
#include <bits/stdc++.h>
const int mod = 666013;
const int inf = 0x3f3f3f3f;
typedef long long ll;
using namespace std;
class InParser {
private:
FILE *fin;
char *buff;
int sp;
char read_ch() {
if (++sp == 4096) {
sp = 0, fread(buff, 1, 4096, fin);
}
return buff[sp];
}
public:
InParser(const char* name) {
fin = fopen(name, "r");
buff = new char[4096]();
sp = 4095;
}
template<typename T>
InParser& operator >> (T &number) {
register T ch, sgn = 1;
number = 0;
while (!isdigit(ch = read_ch()) && ch != '-');
if (ch == '-') {
sgn = -1, ch = read_ch();
}
do {
number = 10 * number + ch - '0';
} while (isdigit(ch = read_ch()));
number *= sgn;
return *this;
}
} fin("secv2.in");
ofstream fout("secv2.out");
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
// Fie suma(i, j) = v[i] + v[i + 1] + ... + v[j]
// suma(i, j) = suma(1, j) - suma(1, i - 1)
// lungimea >= k => j - i + 1 >= k
// => pentru j fixat, i <= j - k + 1
// => i - 1 <= j - k
// Precalculam sumele partiale si minime partiale
// pe sume partiale iar raspunsul pentru capatul drept
// fixat in j (j >= k) este s[j] - mn[j - k]
int n, k;
fin >> n >> k;
vector<int> v(n + 1), s(n + 1), mn(n + 1);
// mn[i] = indicele j, 1 <= j <= i, s[j] minim
for (int i = 1; i <= n; ++i) {
fin >> v[i];
s[i] = s[i - 1] + v[i];
mn[i] = s[mn[i - 1]] < s[i] ? mn[i - 1] : i;
}
int dr = k;
for (int i = k; i <= n; ++i) {
if (s[dr] - s[mn[dr - k]] < s[i] - s[mn[i - k]]) {
dr = i;
}
}
fout << mn[dr - k] + 1 << ' ' << dr << ' ' << s[dr] - s[mn[dr - k]];
}