oj.uz

답안 #443666

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
443666 2021-07-11T08:23:38 Z prvocislo Teams (CEOI11_tea) C++17
100 / 100
 532 ms 34636 KB 
#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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 308 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 448 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 2252 KB Output is correct
2 Correct 34 ms 2512 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 2500 KB Output is correct
2 Correct 30 ms 2380 KB Output is correct
3 Correct 37 ms 3088 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 350 ms 20032 KB Output is correct
2 Correct 336 ms 22456 KB Output is correct
3 Correct 351 ms 24516 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 482 ms 26756 KB Output is correct
2 Correct 495 ms 30912 KB Output is correct
3 Correct 450 ms 29744 KB Output is correct
4 Correct 496 ms 28356 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 417 ms 26720 KB Output is correct
2 Correct 263 ms 34636 KB Output is correct
3 Correct 496 ms 30632 KB Output is correct
4 Correct 532 ms 32452 KB Output is correct