Submission #1084908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084908		PakinDioxide	Rice Hub (IOI11_ricehub)	C++17	68 / 100	1053 ms	3024 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>

using namespace std;

int l = 1, r = 0;
vector <pair <int, int>> p;

long long recal() {
    long long sum = 0;
    int ll = l, rr = r;
    while (ll < rr) sum += p[rr--].first - p[ll++].first;
    return sum;
}

int besthub(int n, int m, int a[], long long x) {
    p.emplace_back(0, 0);
    for (int j = 0; j < n; j++) {
        int i = a[j];
        p.emplace_back(i, p[p.size()-1].second + 1);
        // if (p[p.size()-1].first != i) p.emplace_back(i, p[p.size()-1].second + 1);
        // else p[p.size()-1].second++;
    }
    // for (auto [x, y] : p) printf("%d %d\n", x, y);
    // printf("S %d\n", p.size());
    int mx = 0;
    while (r < p.size() - 1) {
        r++;
        while (recal() > x) l++;
        mx = max(mx, p[r].second - p[l-1].second);
        // printf("MX %d\n", mx);
    }
    return mx;
}

Compilation message (stderr)

ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:27:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     while (r < p.size() - 1) {
      |            ~~^~~~~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 25 / 25
• Subtask 3: 26 / 26
• Subtask 4: 0 / 32