#include <iostream>
#include <vector>
#include <fstream>
#include <sstream>
#include <string>
#include <utility>
 
#if defined(_WIN32)
#include <windows.h>
#elif defined(__linux__) || defined(__APPLE__)
#include <unistd.h>
#endif
 
using namespace std;
 
string getParentPath(const string& filePath) {
    size_t found = filePath.find_last_of("/\\");
    return filePath.substr(0, found);
}
 
typedef pair<string, double> DayData;
typedef vector<DayData> RateData;
 
RateData read_csv(const string &filename) {
    RateData data;
    ifstream file(filename);
    string line;
 
    // to skip the first line because it contains the column names
    getline(file, line);
 
    while (getline(file, line)) {
        stringstream linestream(line);
        string date;
        double value;
        getline(linestream, date, ',');
        linestream >> value;
        data.emplace_back(date, value);
    }
 
    return data;
}
 
void heapify(RateData &arr, int n, int i, bool is_max_heap) {
    int extreme = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
 
    if (left < n && (is_max_heap ? arr[left].second > arr[extreme].second : arr[left].second < arr[extreme].second))
        extreme = left;
 
    if (right < n && (is_max_heap ? arr[right].second > arr[extreme].second : arr[right].second < arr[extreme].second))
        extreme = right;
 
    if (extreme != i) {
        swap(arr[i], arr[extreme]);
        heapify(arr, n, extreme, is_max_heap);
    }
}
 
void build_max_heap(RateData &arr) {
    int n = arr.size();
    int start_index = (n / 2) - 1;
    for (int i = start_index; i >= 0; i--) {
        heapify(arr, n, i, true);
    }
}
 
void build_min_heap(RateData &arr) {
    int n = arr.size();
    int start_index = (n / 2) - 1;
    for (int i = start_index; i >= 0; i--) {
        heapify(arr, n, i, false);
    }
}
 
vector<double> get_changes(RateData &data) {
    vector<double> changes;
    for (size_t i = 1; i < data.size(); i++) {
        changes.push_back(data[i].second - data[i - 1].second);
    }
    return changes;
}
 
double max_subseq_sum(
        const RateData &data,
        string &start_date,
        string &end_date,
        const vector<double> &changes
) {
    double max_so_far = 0, max_ending_here = 0;
    int start = 0, end = 0, s = 0;
 
    for (int i = 0; i < changes.size(); ++i) {
        max_ending_here += changes[i];
 
        if (max_ending_here > max_so_far) {
            max_so_far = max_ending_here;
            start = s;
            end = i;
        } else if (max_ending_here < 0) {
            max_ending_here = 0;
            s = i + 1;
        }
    }
 
    start_date = data[start + 1].first;
    end_date = data[end + 1].first;
    return max_so_far;
}
 
RateData get_extremes(RateData &heap, bool is_max, int N) {
    RateData extremes;
 
    if (is_max) {
        build_max_heap(heap);
    } else {
        build_min_heap(heap);
    }
 
    for (int i = 0; i < N; ++i) {
        extremes.push_back(heap[0]);
        heap[0] = heap.back();
        heap.pop_back();
        heapify(heap, heap.size(), 0, is_max);
    }
    return extremes;
}
 
void print_extremes(const RateData &extremes, const string &label) {
    cout << label << " days:" << endl;
    for (const auto &day: extremes) {
        cout << "Date: " << day.first << ", Change: " << day.second << endl;
    }
}
 
int main() {
    int num_days;
    cout << "Number of days: ";
    cin >> num_days;
 
    // Manually specify the file path
    string filename = "euro-dollar.csv";
 
    auto data = read_csv(filename);
    auto changes = get_changes(data);
 
    string start_date, end_date;
    double max_sum = max_subseq_sum(data, start_date, end_date, changes);
 
    cout << "The maximum subsequence sum is: " << max_sum << endl;
    cout << "Start date: " << start_date << ", End date: " << end_date << endl;
 
    RateData changes_for_heap;
    for (int i = 0; i < data.size() - 1; ++i) {
        double change = data[i + 1].second - data[i].second;
        changes_for_heap.emplace_back(data[i + 1].first, change);
    }
 
    // find the N highest days
    auto maximum_heap = changes_for_heap;
    auto highest_days = get_extremes(maximum_heap, true, num_days);
    print_extremes(highest_days, "Highest");
 
    // find the N lowest days
    RateData minimum_heap = changes_for_heap;
    RateData lowest_days = get_extremes(minimum_heap, false, num_days);
    print_extremes(lowest_days, "Lowest");
 
    return 0;
}
 
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8ZnN0cmVhbT4KI2luY2x1ZGUgPHNzdHJlYW0+CiNpbmNsdWRlIDxzdHJpbmc+CiNpbmNsdWRlIDx1dGlsaXR5PgoKI2lmIGRlZmluZWQoX1dJTjMyKQojaW5jbHVkZSA8d2luZG93cy5oPgojZWxpZiBkZWZpbmVkKF9fbGludXhfXykgfHwgZGVmaW5lZChfX0FQUExFX18pCiNpbmNsdWRlIDx1bmlzdGQuaD4KI2VuZGlmCgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKc3RyaW5nIGdldFBhcmVudFBhdGgoY29uc3Qgc3RyaW5nJiBmaWxlUGF0aCkgewogICAgc2l6ZV90IGZvdW5kID0gZmlsZVBhdGguZmluZF9sYXN0X29mKCIvXFwiKTsKICAgIHJldHVybiBmaWxlUGF0aC5zdWJzdHIoMCwgZm91bmQpOwp9Cgp0eXBlZGVmIHBhaXI8c3RyaW5nLCBkb3VibGU+IERheURhdGE7CnR5cGVkZWYgdmVjdG9yPERheURhdGE+IFJhdGVEYXRhOwoKUmF0ZURhdGEgcmVhZF9jc3YoY29uc3Qgc3RyaW5nICZmaWxlbmFtZSkgewogICAgUmF0ZURhdGEgZGF0YTsKICAgIGlmc3RyZWFtIGZpbGUoZmlsZW5hbWUpOwogICAgc3RyaW5nIGxpbmU7CgogICAgLy8gdG8gc2tpcCB0aGUgZmlyc3QgbGluZSBiZWNhdXNlIGl0IGNvbnRhaW5zIHRoZSBjb2x1bW4gbmFtZXMKICAgIGdldGxpbmUoZmlsZSwgbGluZSk7CgogICAgd2hpbGUgKGdldGxpbmUoZmlsZSwgbGluZSkpIHsKICAgICAgICBzdHJpbmdzdHJlYW0gbGluZXN0cmVhbShsaW5lKTsKICAgICAgICBzdHJpbmcgZGF0ZTsKICAgICAgICBkb3VibGUgdmFsdWU7CiAgICAgICAgZ2V0bGluZShsaW5lc3RyZWFtLCBkYXRlLCAnLCcpOwogICAgICAgIGxpbmVzdHJlYW0gPj4gdmFsdWU7CiAgICAgICAgZGF0YS5lbXBsYWNlX2JhY2soZGF0ZSwgdmFsdWUpOwogICAgfQoKICAgIHJldHVybiBkYXRhOwp9Cgp2b2lkIGhlYXBpZnkoUmF0ZURhdGEgJmFyciwgaW50IG4sIGludCBpLCBib29sIGlzX21heF9oZWFwKSB7CiAgICBpbnQgZXh0cmVtZSA9IGk7CiAgICBpbnQgbGVmdCA9IDIgKiBpICsgMTsKICAgIGludCByaWdodCA9IDIgKiBpICsgMjsKCiAgICBpZiAobGVmdCA8IG4gJiYgKGlzX21heF9oZWFwID8gYXJyW2xlZnRdLnNlY29uZCA+IGFycltleHRyZW1lXS5zZWNvbmQgOiBhcnJbbGVmdF0uc2Vjb25kIDwgYXJyW2V4dHJlbWVdLnNlY29uZCkpCiAgICAgICAgZXh0cmVtZSA9IGxlZnQ7CgogICAgaWYgKHJpZ2h0IDwgbiAmJiAoaXNfbWF4X2hlYXAgPyBhcnJbcmlnaHRdLnNlY29uZCA+IGFycltleHRyZW1lXS5zZWNvbmQgOiBhcnJbcmlnaHRdLnNlY29uZCA8IGFycltleHRyZW1lXS5zZWNvbmQpKQogICAgICAgIGV4dHJlbWUgPSByaWdodDsKCiAgICBpZiAoZXh0cmVtZSAhPSBpKSB7CiAgICAgICAgc3dhcChhcnJbaV0sIGFycltleHRyZW1lXSk7CiAgICAgICAgaGVhcGlmeShhcnIsIG4sIGV4dHJlbWUsIGlzX21heF9oZWFwKTsKICAgIH0KfQoKdm9pZCBidWlsZF9tYXhfaGVhcChSYXRlRGF0YSAmYXJyKSB7CiAgICBpbnQgbiA9IGFyci5zaXplKCk7CiAgICBpbnQgc3RhcnRfaW5kZXggPSAobiAvIDIpIC0gMTsKICAgIGZvciAoaW50IGkgPSBzdGFydF9pbmRleDsgaSA+PSAwOyBpLS0pIHsKICAgICAgICBoZWFwaWZ5KGFyciwgbiwgaSwgdHJ1ZSk7CiAgICB9Cn0KCnZvaWQgYnVpbGRfbWluX2hlYXAoUmF0ZURhdGEgJmFycikgewogICAgaW50IG4gPSBhcnIuc2l6ZSgpOwogICAgaW50IHN0YXJ0X2luZGV4ID0gKG4gLyAyKSAtIDE7CiAgICBmb3IgKGludCBpID0gc3RhcnRfaW5kZXg7IGkgPj0gMDsgaS0tKSB7CiAgICAgICAgaGVhcGlmeShhcnIsIG4sIGksIGZhbHNlKTsKICAgIH0KfQoKdmVjdG9yPGRvdWJsZT4gZ2V0X2NoYW5nZXMoUmF0ZURhdGEgJmRhdGEpIHsKICAgIHZlY3Rvcjxkb3VibGU+IGNoYW5nZXM7CiAgICBmb3IgKHNpemVfdCBpID0gMTsgaSA8IGRhdGEuc2l6ZSgpOyBpKyspIHsKICAgICAgICBjaGFuZ2VzLnB1c2hfYmFjayhkYXRhW2ldLnNlY29uZCAtIGRhdGFbaSAtIDFdLnNlY29uZCk7CiAgICB9CiAgICByZXR1cm4gY2hhbmdlczsKfQoKZG91YmxlIG1heF9zdWJzZXFfc3VtKAogICAgICAgIGNvbnN0IFJhdGVEYXRhICZkYXRhLAogICAgICAgIHN0cmluZyAmc3RhcnRfZGF0ZSwKICAgICAgICBzdHJpbmcgJmVuZF9kYXRlLAogICAgICAgIGNvbnN0IHZlY3Rvcjxkb3VibGU+ICZjaGFuZ2VzCikgewogICAgZG91YmxlIG1heF9zb19mYXIgPSAwLCBtYXhfZW5kaW5nX2hlcmUgPSAwOwogICAgaW50IHN0YXJ0ID0gMCwgZW5kID0gMCwgcyA9IDA7CgogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBjaGFuZ2VzLnNpemUoKTsgKytpKSB7CiAgICAgICAgbWF4X2VuZGluZ19oZXJlICs9IGNoYW5nZXNbaV07CgogICAgICAgIGlmIChtYXhfZW5kaW5nX2hlcmUgPiBtYXhfc29fZmFyKSB7CiAgICAgICAgICAgIG1heF9zb19mYXIgPSBtYXhfZW5kaW5nX2hlcmU7CiAgICAgICAgICAgIHN0YXJ0ID0gczsKICAgICAgICAgICAgZW5kID0gaTsKICAgICAgICB9IGVsc2UgaWYgKG1heF9lbmRpbmdfaGVyZSA8IDApIHsKICAgICAgICAgICAgbWF4X2VuZGluZ19oZXJlID0gMDsKICAgICAgICAgICAgcyA9IGkgKyAxOwogICAgICAgIH0KICAgIH0KCiAgICBzdGFydF9kYXRlID0gZGF0YVtzdGFydCArIDFdLmZpcnN0OwogICAgZW5kX2RhdGUgPSBkYXRhW2VuZCArIDFdLmZpcnN0OwogICAgcmV0dXJuIG1heF9zb19mYXI7Cn0KClJhdGVEYXRhIGdldF9leHRyZW1lcyhSYXRlRGF0YSAmaGVhcCwgYm9vbCBpc19tYXgsIGludCBOKSB7CiAgICBSYXRlRGF0YSBleHRyZW1lczsKCiAgICBpZiAoaXNfbWF4KSB7CiAgICAgICAgYnVpbGRfbWF4X2hlYXAoaGVhcCk7CiAgICB9IGVsc2UgewogICAgICAgIGJ1aWxkX21pbl9oZWFwKGhlYXApOwogICAgfQoKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgTjsgKytpKSB7CiAgICAgICAgZXh0cmVtZXMucHVzaF9iYWNrKGhlYXBbMF0pOwogICAgICAgIGhlYXBbMF0gPSBoZWFwLmJhY2soKTsKICAgICAgICBoZWFwLnBvcF9iYWNrKCk7CiAgICAgICAgaGVhcGlmeShoZWFwLCBoZWFwLnNpemUoKSwgMCwgaXNfbWF4KTsKICAgIH0KICAgIHJldHVybiBleHRyZW1lczsKfQoKdm9pZCBwcmludF9leHRyZW1lcyhjb25zdCBSYXRlRGF0YSAmZXh0cmVtZXMsIGNvbnN0IHN0cmluZyAmbGFiZWwpIHsKICAgIGNvdXQgPDwgbGFiZWwgPDwgIiBkYXlzOiIgPDwgZW5kbDsKICAgIGZvciAoY29uc3QgYXV0byAmZGF5OiBleHRyZW1lcykgewogICAgICAgIGNvdXQgPDwgIkRhdGU6ICIgPDwgZGF5LmZpcnN0IDw8ICIsIENoYW5nZTogIiA8PCBkYXkuc2Vjb25kIDw8IGVuZGw7CiAgICB9Cn0KCmludCBtYWluKCkgewogICAgaW50IG51bV9kYXlzOwogICAgY291dCA8PCAiTnVtYmVyIG9mIGRheXM6ICI7CiAgICBjaW4gPj4gbnVtX2RheXM7CgogICAgLy8gTWFudWFsbHkgc3BlY2lmeSB0aGUgZmlsZSBwYXRoCiAgICBzdHJpbmcgZmlsZW5hbWUgPSAiZXVyby1kb2xsYXIuY3N2IjsKCiAgICBhdXRvIGRhdGEgPSByZWFkX2NzdihmaWxlbmFtZSk7CiAgICBhdXRvIGNoYW5nZXMgPSBnZXRfY2hhbmdlcyhkYXRhKTsKCiAgICBzdHJpbmcgc3RhcnRfZGF0ZSwgZW5kX2RhdGU7CiAgICBkb3VibGUgbWF4X3N1bSA9IG1heF9zdWJzZXFfc3VtKGRhdGEsIHN0YXJ0X2RhdGUsIGVuZF9kYXRlLCBjaGFuZ2VzKTsKCiAgICBjb3V0IDw8ICJUaGUgbWF4aW11bSBzdWJzZXF1ZW5jZSBzdW0gaXM6ICIgPDwgbWF4X3N1bSA8PCBlbmRsOwogICAgY291dCA8PCAiU3RhcnQgZGF0ZTogIiA8PCBzdGFydF9kYXRlIDw8ICIsIEVuZCBkYXRlOiAiIDw8IGVuZF9kYXRlIDw8IGVuZGw7CgogICAgUmF0ZURhdGEgY2hhbmdlc19mb3JfaGVhcDsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgZGF0YS5zaXplKCkgLSAxOyArK2kpIHsKICAgICAgICBkb3VibGUgY2hhbmdlID0gZGF0YVtpICsgMV0uc2Vjb25kIC0gZGF0YVtpXS5zZWNvbmQ7CiAgICAgICAgY2hhbmdlc19mb3JfaGVhcC5lbXBsYWNlX2JhY2soZGF0YVtpICsgMV0uZmlyc3QsIGNoYW5nZSk7CiAgICB9CgogICAgLy8gZmluZCB0aGUgTiBoaWdoZXN0IGRheXMKICAgIGF1dG8gbWF4aW11bV9oZWFwID0gY2hhbmdlc19mb3JfaGVhcDsKICAgIGF1dG8gaGlnaGVzdF9kYXlzID0gZ2V0X2V4dHJlbWVzKG1heGltdW1faGVhcCwgdHJ1ZSwgbnVtX2RheXMpOwogICAgcHJpbnRfZXh0cmVtZXMoaGlnaGVzdF9kYXlzLCAiSGlnaGVzdCIpOwoKICAgIC8vIGZpbmQgdGhlIE4gbG93ZXN0IGRheXMKICAgIFJhdGVEYXRhIG1pbmltdW1faGVhcCA9IGNoYW5nZXNfZm9yX2hlYXA7CiAgICBSYXRlRGF0YSBsb3dlc3RfZGF5cyA9IGdldF9leHRyZW1lcyhtaW5pbXVtX2hlYXAsIGZhbHNlLCBudW1fZGF5cyk7CiAgICBwcmludF9leHRyZW1lcyhsb3dlc3RfZGF5cywgIkxvd2VzdCIpOwoKICAgIHJldHVybiAwOwp9Cgo=