oj.uz

Submission #804306

# Submission time Handle Problem Language Result Execution time Memory
804306 2023-08-03T07:56:49 Z moel_solution(#10136) Fun Palace (CCO18_fun) C++17
0 / 25
 1 ms 340 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
void app(int&x,int y)
{
    x=max(x,y);
    return;
}
const int MX=50;
int dp[1010][MX][MX];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,e;
    cin>>n;
    cin>>e;
    vector<pi>v(n-1);
    for(pi&t:v)
        cin>>t.fi>>t.se;
    for(int i=n-1;i>0;i--)
    {
        pi crt=v[i-1];
        for(int j=0;j<MX;j++)
        {
            for(int k=0;k<1;k++)
            {
                for(int j2=0;j2<=min(MX-1,dp[i][j][k]);j2++)
                {
                    if(j2>=crt.fi+crt.se)
                        app(dp[i-1][j2][k],j2);
                    else if(j2>=crt.se)
                    {
                        int nk=k;
                        app(dp[i-1][j2-crt.se][nk],j2);
                    }
                    else if(j+k<crt.se)
                    {
                        int nk=crt.fi+k;
                        app(dp[i-1][0][nk],j2);
                    }
                    else
                    {
                        int nk=max(crt.fi+crt.se-j2,k);
                        app(dp[i-1][0][nk],j2);
                    }
                }
            }
            for(int k=1;k<MX;k++)
            {
                if(j<MX-1)
                    app(dp[i][j+1][k-1],dp[i][j][k]+1);
                if(j>=crt.fi+crt.se)
                    app(dp[i-1][j][k],dp[i][j][k]);
                else if(j>=crt.se)
                {
                    int nk=k;
                    app(dp[i-1][j-crt.se][nk],dp[i][j][k]);
                }
                else if(j+k<crt.se)
                {
                    int nk=crt.fi+k;
                    app(dp[i-1][0][nk],dp[i][j][k]);
                }
                else
                {
                    int nk=max(crt.fi+crt.se-j,k);
                    app(dp[i-1][0][nk],dp[i][j][k]);
                }
            }
        }
    }
    int ans=e-1;
    for(int j=0;j<e;j++)
        for(int i=0;i<MX;i++)
            ans=max(ans,dp[0][j][i]);
    cout<<ans<<endl;
    return 0;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -