oj.uz

Submission #846840

# Submission time Handle Problem Language Result Execution time Memory
846840 2023-09-08T14:06:32 Z Abito Financial Report (JOI21_financial) C++17
12 / 100
 58 ms 21072 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
#define endl '\n'
#define elif else if
#define pow pwr
#define sqrt sqrtt
//#define int long long
#define y1 YONE
typedef unsigned long long ull;
using namespace std;
const int N=3e5+5,M=405;
int a[N],n,d,bit[N],lis[N],b[N],dp[M][M][M];
bool vis[M][M][M];
void edit(int x){
    while (x<=n){
        bit[x]++;
        x+=x&-x;
    }return;
}int query(int x){
    int y=0;
    while (x){
        y+=bit[x];
        x-=x&-x;
    }return y;
}
int rec(int i,int last,int mx){
    //cout<<i<<' '<<last<<' '<<mx<<endl;
    if (i-last>d) return INT_MIN;
    if (i>n && last!=n) return INT_MIN;
    if (i>n) return 0;
    if (vis[i][last][mx]) return dp[i][last][mx];
    vis[i][last][mx]=true;
    int nextmx=mx;
    if (a[i]>a[mx]) nextmx=i;
    return dp[i][last][mx]=max(rec(i+1,last,mx),rec(i+1,i,nextmx)+bool(nextmx==i));
}
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>n>>d;
    for (int i=1;i<=n;i++) cin>>a[i];
    if (d==1){
        stack<int> s;
        for (int i=1;i<=n;i++){
            while (!s.empty()){
                if (a[s.top()]<a[i]) s.pop();
                else{
                    b[i]=s.top();
                    break;
                }
            }s.push(i);
        }
        int ans=0;
        for (int i=n;i;i--){
            edit(b[i]+1);
            ans=max(ans,query(i));
        }cout<<ans<<endl;
        return 0;
    }cout<<rec(1,0,0)<<endl;
    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4440 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Incorrect 1 ms 4444 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4440 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Incorrect 1 ms 4444 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4440 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Incorrect 1 ms 4444 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 5980 KB Output is correct
2 Correct 32 ms 4920 KB Output is correct
3 Correct 37 ms 4700 KB Output is correct
4 Correct 47 ms 4728 KB Output is correct
5 Correct 32 ms 4688 KB Output is correct
6 Correct 47 ms 4760 KB Output is correct
7 Correct 46 ms 3440 KB Output is correct
8 Correct 28 ms 5980 KB Output is correct
9 Correct 37 ms 4696 KB Output is correct
10 Correct 35 ms 5308 KB Output is correct
11 Correct 34 ms 4700 KB Output is correct
12 Correct 40 ms 4696 KB Output is correct
13 Correct 33 ms 4708 KB Output is correct
14 Correct 29 ms 4700 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 58 ms 21072 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4440 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Incorrect 1 ms 4444 KB Output isn't correct
14 Halted 0 ms 0 KB -