Submission #541316

#	Time	Username	Problem	Language	Result	Execution time	Memory
541316		Jomnoi	Financial Report (JOI21_financial)	C++17	5 / 100	48 ms	3784 KiB

Main

#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;

const int N = 3e5 + 10;

int a[N];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, d;
    cin >> n >> d;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    int ans = 0;
    if(d == 1) {
        int ma = 0, cnt = 1;
        for(int i = 2; i <= n; i++) {
            if(a[i - 1] < a[i]) {
                cnt++;
            }
            else {
                cnt = 1;
            }
            ma = max(ma, cnt);
        }
        ans = ma;
    }
    else if(d == n) {
        vector <int> lis;
        for(int i = 1; i <= n; i++) {
            auto it = lower_bound(lis.begin(), lis.end(), a[i]);
            if(it == lis.end()) {
                lis.push_back(a[i]);
            }
            else {
                *it = a[i];
            }
        }
        ans = lis.size();
    }
    else if(n <= 20) {
        for(int r = 0; r < (1<<n); r++) {
            vector <pair <int, int>> vec;
            for(int i = 0; i < n; i++) {
                if(r & (1<<i)) {
                    vec.emplace_back(a[i + 1], i + 1);
                }
            }

            if(vec.empty()) {
                continue;
            }

            int ma = vec[0].first, cnt = 1;
            for(int i = 1; i < vec.size(); i++) {
                if(vec[i].second - vec[i - 1].second > d) {
                    cnt = 0;
                    break;
                }

                if(ma < vec[i].first) {
                    ma = vec[i].first;
                    cnt++;
                }
            }
            ans = max(ans, cnt);
        }
    }
    else {
        assert(false);
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:58:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             for(int i = 1; i < vec.size(); i++) {
      |                            ~~^~~~~~~~~~~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 20
• Subtask 4: 0 / 12
• Subtask 5: 5 / 5
• Subtask 6: 0 / 35