Submission #443666

#	Time	Username	Problem	Language	Result	Execution time	Memory
443666		prvocislo	Teams (CEOI11_tea)	C++17	100 / 100	532 ms	34636 KiB

tea

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int inf = 1e9;
struct kid { int a, i; };
bool cmp(const kid &a, const kid &b) { return a.a < b.a; }
int n;
vector<kid> v;
vector<int> dp, pv, nn;
int max_teams(int l)
{
    dp.assign(n+1, 0), pv.assign(n+1, -1), nn.assign(n+1, 0);
    dp[0] = 0; // dp[i] = najvacsi pocet timov ak sme uz pouzili prvych i deti
    int maxi = 0;
    for (int i = 1; i <= n; i++)
    {
        if (v[i].a > i) dp[i] = -inf;
        else 
        {
            int j = nn[i-v[i].a];
            if (i-j > l) dp[i] = -inf;
            else dp[i] = dp[j]+1, pv[i] = j;
            if (dp[i] < dp[nn[i-1]] && i != n) dp[i] = -inf;
        }
        maxi = max(maxi, dp[i]);
        if (dp[i] != -inf) nn[i] = i;
        else nn[i] = nn[i-1];
    }
    return dp[n];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); 
    cin >> n;
    v.resize(n+1);
    for (int i = 1; i <= n; i++) 
        cin >> v[i].a, v[i].i = i;
    sort(v.begin()+1, v.end(), cmp);
    int maxi = max_teams(n);
    int lo = v[n].a, hi = n;
    while (lo < hi)
    {
        int mi = (lo + hi) >> 1;
        if (max_teams(mi) == maxi) hi = mi;
        else lo = mi+1;
    }
    cout << max_teams(lo) << "\n";
    int r = n;
    while (r)
    {
        cout << r - pv[r];
        for (int i = pv[r]+1; i <= r; i++) cout << " " << v[i].i;
        cout << "\n";
        r = pv[r];
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10