86302024-01-24 09:15:07MagyarKendeSZLGTűzijátékcpp17Time limit exceeded 10/50400ms63892 KiB

#include <bits/stdc++.h>

#pragma region Utility

#define speed cin.tie(0); ios::sync_with_stdio(0)
#define cinv(v) for (auto& e : v) cin >> e;

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define size(v) (int)v.size()
#define has(s, e) s.count(e)

#define max_index(v) max_element(all(v)) - v.begin()
#define min_index(v) min_element(all(v)) - v.begin()
#define smax(x, y) x = max(x, y)
#define smin(x, y) x = min(x, y)

#define sum(v) accumulate(all(v), 0)
#define product(v, T) accumulate(all(v), 1, multiplies<T>())

using namespace std;
using ll = long long;
using point = array<int, 2>;

int max(point p) { return max(p[0], p[1]); }
int min(point p) { return min(p[0], p[1]); }

template <typename T>
vector<T> prefix_sum(const vector<T>& v) {
    vector<T> result(size(v));
    partial_sum(all(v), result.begin());
    return result;
}

#pragma endregion


int main() {
    #ifdef ONLINE_JUDGE
    speed;
    #else
    #define cin fin
    #endif

    ifstream fin("input.txt");

    int N, S, T;
    cin >> N >> S >> T;
    vector<int> input(N);
    cinv(input);

    S--;

    vector<point> distS({{0, 0}});
    unordered_map<int, int> index_conv;

    for (int i = 0; i < N; i++) {
        if (i != S && abs(input[i] - input[S]) < T) {
            continue;
        }
        distS.push_back({input[i], i});
        index_conv[size(distS) - 1] = i + 1;
    }

    N = size(distS) - 1;

    vector<point> dp(N + 1);
    dp[1][0] = 1;

    for (int i = 2; i <= N; i++) {
        dp[i] = {1, 0};
        for (int j = 1; j < i; j++) {
            if (distS[i][0] - distS[j][0] < T) {
                break;
            }
            if (dp[i][0] < dp[j][0] + 1) {
                dp[i][0] = dp[j][0] + 1;
                dp[i][1] = index_conv[j];
            }
        }
    }

    cout << dp[N][0] << '\n';

    int maxi = max_index(dp);
    
    vector<int> result({index_conv[maxi]});
    int curr = dp[maxi][1];

    while (curr) {
        result.push_back(curr);
        curr = dp[curr][1];
    }

    sort(all(result));
    for (int x : result) cout << x << ' ';

}
SubtaskSumTestVerdictTimeMemory
base10/50
1Accepted0/03ms1828 KiB
2Time limit exceeded0/0400ms8420 KiB
3Accepted2/23ms2908 KiB
4Accepted2/23ms2988 KiB
5Accepted2/23ms3120 KiB
6Accepted2/23ms3340 KiB
7Accepted2/23ms3552 KiB
8Wrong answer0/23ms3672 KiB
9Runtime error0/2168ms63892 KiB
10Wrong answer0/2238ms4140 KiB
11Time limit exceeded0/2303ms63836 KiB
12Time limit exceeded0/2354ms3752 KiB
13Time limit exceeded0/2374ms4028 KiB
14Time limit exceeded0/2333ms4348 KiB
15Time limit exceeded0/3377ms4516 KiB
16Time limit exceeded0/3370ms5916 KiB
17Time limit exceeded0/3352ms6668 KiB
18Time limit exceeded0/3372ms8092 KiB
19Time limit exceeded0/3354ms11988 KiB
20Time limit exceeded0/3358ms12936 KiB
21Time limit exceeded0/4349ms13712 KiB
22Time limit exceeded0/4363ms14648 KiB