oj.uz

Submission #497398

# Submission time Handle Problem Language Result Execution time Memory
497398 2021-12-23T04:28:09 Z SirCovidThe19th Teams (CEOI11_tea) C++17
100 / 100
 383 ms 31668 KB 
#include <bits/stdc++.h>
using namespace std; 

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    int n; cin >> n; pair<int, int> A[n + 1]; 
    for (int i = 1; i <= n; i++) cin >> A[i].first, A[i].second = i;
    sort(A + 1, A + n + 1);

    auto maxTeams = [&](int mxsz, bool get){
        int dp[n + 1], sz[n + 1], lft[n + 1]; 
        memset(dp, -0x3f, sizeof(dp)); dp[0] = lft[0] = 0;

        for (int i = 1; i <= n; i++){
            int l = max(i - mxsz, 0), r = i - A[i].first;
            if (r >= 0 and l <= lft[r]){
                dp[i] = dp[lft[r]] + 1; sz[i] = i - lft[r];
                if (i != n and dp[lft[i - 1]] > dp[i]) dp[i] = -1e9; //not optimal to transition from i
            }
            lft[i] = (dp[i] >= 0) ? i : lft[i - 1];
        }
        if (get){
            cout<<dp[n]<<"\n";
            for (int pos = n; pos; pos -= sz[pos]){
                cout<<sz[pos]<<" ";
                for (int i = pos; i > pos - sz[pos]; i--) cout<<A[i].second<<" ";
                cout<<"\n";
            }
        }
        return dp[n];
    };    
    int L = 1, H = n, mx = maxTeams(1e9, 0);
    while (L < H){
        int M = (L + H) / 2;
        (maxTeams(M, 0) == mx) ? H = M : L = M + 1;
    }
    maxTeams(H, 1);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 312 KB Output is correct
2 Correct 1 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 204 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory 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 #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 300 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 296 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 444 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 332 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 456 KB Output is correct
2 Correct 2 ms 332 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2684 KB Output is correct
2 Correct 23 ms 2572 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3000 KB Output is correct
2 Correct 22 ms 2420 KB Output is correct
3 Correct 26 ms 3064 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 23700 KB Output is correct
2 Correct 245 ms 22292 KB Output is correct
3 Correct 252 ms 23132 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 30860 KB Output is correct
2 Correct 331 ms 31668 KB Output is correct
3 Correct 311 ms 29732 KB Output is correct
4 Correct 295 ms 26628 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 30920 KB Output is correct
2 Correct 271 ms 30976 KB Output is correct
3 Correct 316 ms 30624 KB Output is correct
4 Correct 383 ms 29804 KB Output is correct