oj.uz

Submission #264613

# Submission time Handle Problem Language Result Execution time Memory
264613 2020-08-14T08:00:17 Z 반딧불(#5094) Teams (CEOI11_tea) C++17
100 / 100
 458 ms 32556 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
pair<int, int> arr[1000002];
int DP[1000002], DP2[1000002];
int track[1000002];

int getAns(int x){
    for(int i=1; i<=n; i++){
        DP[i] = -1e9, DP2[i] = DP2[i-1];
        int tmp = i - arr[i].first;
        if(tmp < 0) continue;
        tmp = DP2[tmp];
        if(i - tmp > x) continue;
        DP[i] = DP[tmp] + 1;
        track[i] = tmp;

        if(DP[i] >= DP[DP2[i]]){
            DP2[i] = i;
        }
    }
    return DP[n];
}

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        int x;
        scanf("%d", &x);
        arr[i] = {x, i};
    }

    sort(arr+1, arr+n+1);
    int ans = getAns(n);

    int l = arr[n].first, r = n-1, key = n;
    while(l <= r){
        int m = (l+r)>>1;
        if(getAns(m) == ans) r = m-1, key = m;
        else l = m+1;
    }

    getAns(key);
    printf("%d\n", ans);
    while(n){
        printf("%d ", n - track[n]);
        for(int i=track[n]+1; i<=n; i++) printf("%d ", arr[i].second);
        puts("");
        n = track[n];
    }
}

Compilation message

tea.cpp: In function 'int main()':
tea.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
tea.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 544 KB Output is correct
2 Correct 2 ms 512 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2808 KB Output is correct
2 Correct 30 ms 2688 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 3064 KB Output is correct
2 Correct 29 ms 2552 KB Output is correct
3 Correct 37 ms 3064 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 20492 KB Output is correct
2 Correct 309 ms 22392 KB Output is correct
3 Correct 347 ms 24440 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 32404 KB Output is correct
2 Correct 458 ms 31736 KB Output is correct
3 Correct 412 ms 29816 KB Output is correct
4 Correct 432 ms 28512 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 32132 KB Output is correct
2 Correct 282 ms 30712 KB Output is correct
3 Correct 413 ms 30712 KB Output is correct
4 Correct 456 ms 32556 KB Output is correct