oj.uz

답안 #491663

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
491663 2021-12-03T18:28:37 Z Bench0310 Teams (CEOI11_tea) C++17
100 / 100
 476 ms 21032 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<array<int,2>> a(n+1,{0,0});
    for(int i=1;i<=n;i++)
    {
        cin >> a[i][0];
        a[i][1]=i;
    }
    sort(a.begin(),a.end());
    vector<int> p(n+1,0);
    auto go=[&](int lim)->int
    {
        vector<int> dp(n+1,-1);
        dp[0]=0;
        vector<int> prv(n+1,0);
        int mx=0;
        for(int i=1;i<=n;i++)
        {
            prv[i]=prv[i-1];
            if(a[i][0]>i) continue;
            int j=prv[i-a[i][0]];
            if(i-lim<=j&&((i<n&&dp[j]+1>=mx)||i==n))
            {
                dp[i]=dp[j]+1;
                mx=dp[i];
                prv[i]=i;
                p[i]=j;
            }
        }
        return dp[n];
    };
    int cnt=go(n);
    int l=0,r=n;
    while(l<r-1)
    {
        int m=(l+r)/2;
        if(go(m)==cnt) r=m;
        else l=m;
    }
    cout << cnt << "\n";
    go(r);
    int idx=n;
    while(idx>=1)
    {
        cout << idx-p[idx] << " ";
        for(int i=p[idx]+1;i<=idx;i++) cout << a[i][1] << " \n"[i==idx];
        idx=p[idx];
    }
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
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 0 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 0 ms 204 KB Output is correct
3 Correct 0 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 448 KB Output is correct
3 Correct 2 ms 332 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 27 ms 1888 KB Output is correct
2 Correct 27 ms 1892 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 2116 KB Output is correct
2 Correct 26 ms 1816 KB Output is correct
3 Correct 31 ms 2216 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 303 ms 15012 KB Output is correct
2 Correct 309 ms 15096 KB Output is correct
3 Correct 317 ms 15112 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 392 ms 19940 KB Output is correct
2 Correct 476 ms 21032 KB Output is correct
3 Correct 424 ms 19952 KB Output is correct
4 Correct 385 ms 17732 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 397 ms 20024 KB Output is correct
2 Correct 323 ms 19964 KB Output is correct
3 Correct 391 ms 19948 KB Output is correct
4 Correct 413 ms 20204 KB Output is correct