#include <iostream> #include <cmath> #include<vector> #include <algorithm> using namespace std; int N = 201719; int* t = new int[N]; int curr_i = 0; int max_idx = 0; int maxI = 0; void shift(int* t) { for (int i = 0; i <= max_idx; i++) { t[i] = t[i+1]; } } void add(int a) { int i = a - curr_i; max_idx = max(i, max_idx); int v = t[i]; if(v == 0) { t[i] = 1; maxI = max(maxI, i+curr_i); } else if (v == 1) { t[i] = 0; add(a+1); } } int main(int argc, const char* argv[]) { size_t n; cin >> n; std::vector<int> vs (n); for(int i = 0; i < n; i++ ) { string a; cin >> a; vs[i] = stoi(a); } std::sort(vs.begin(), vs.end()); for(auto v : vs) { if(curr_i < v) { shift(t); curr_i = v; } add(v); } cout << maxI << endl; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | #include <iostream> #include <cmath> #include<vector> #include <algorithm> using namespace std; int N = 201719; int* t = new int[N]; int curr_i = 0; int max_idx = 0; int maxI = 0; void shift(int* t) { for (int i = 0; i <= max_idx; i++) { t[i] = t[i+1]; } } void add(int a) { int i = a - curr_i; max_idx = max(i, max_idx); int v = t[i]; if(v == 0) { t[i] = 1; maxI = max(maxI, i+curr_i); } else if (v == 1) { t[i] = 0; add(a+1); } } int main(int argc, const char* argv[]) { size_t n; cin >> n; std::vector<int> vs (n); for(int i = 0; i < n; i++ ) { string a; cin >> a; vs[i] = stoi(a); } std::sort(vs.begin(), vs.end()); for(auto v : vs) { if(curr_i < v) { shift(t); curr_i = v; } add(v); } cout << maxI << endl; } |