oj.uz

Submission #1075577

# Submission time Handle Problem Language Result Execution time Memory
1075577 2024-08-26T07:48:13 Z Faisal_Saqib Catfish Farm (IOI22_fish) C++17
15 / 100
 1000 ms 199976 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define all(x) begin(x),end(x)
const int N=1e5+10;
map<ll,ll> pre[N];
map<ll,ll> dp[N][3];
vll possible[N];
vector<pair<ll,ll>> values[N];
ll solve(ll&n,ll&m,vll&x,vll&y,vll&w)
{
    ll ans=0;
    for(int j=0;j<m;j++)
    {
        values[x[j]].push_back({y[j]+1,w[j]});
        possible[x[j]].push_back(y[j]+1),possible[x[j]+1].push_back(y[j]+1);
        if(x[j]>0)
            possible[x[j]-1].push_back(y[j]+1);
    }
    for(int i=0;i<=n;i++)
    {
        possible[i].push_back(0);
        sort(begin(possible[i]),end(possible[i]));
        sort(begin(values[i]),end(values[i]));
        ll sm=0;
        int pp=0;
        for(auto&j:possible[i])
        {
            while(pp<values[i].size() and values[i][pp].first<=j)
            {
                sm+=values[i][pp].second;
                pp++;
            }
            pre[i][j]=sm;
        }
    }
    // for(int i=0;i<n;i++)
    //     for(int j=0;j<=n;j++)
    //         for(int k=0;k<2;k++)
    //             dp[i][j][k]=0;
    for(auto&h:possible[0])
    {
        dp[0][0][h]=0;
        dp[0][1][h]=0;
    }
    for(int i=1;i<n;i++)
    {
        // ll sum=0;
        ll mx1=-2e18;
        ll mx2=-2e18;
        ll mx11=0,mx22=0;
        for(auto&ip:dp[i-1][0])
        {
            int hp=ip.first;
            mx11=max(mx11,ip.second);

            mx1=max(mx1,ip.second-pre[i-1][hp]);
        }
        for(auto&ip:dp[i-1][1])
        {
            int hp=ip.first;
            mx22=max(mx22,ip.second);
            mx2=max(mx2,ip.second+pre[i][hp]);
        }
        for(auto&h:possible[i])
        {
            dp[i][0][h]=max(dp[i][0][h],mx1+pre[i-1][h]);
            dp[i][1][h]=max(dp[i][1][h],mx1+pre[i-1][h]);
            dp[i][1][h]=max(dp[i][1][h],mx2-pre[i][h]);

            dp[i][0][h]=max(dp[i][0][h],mx11);
            dp[i][0][h]=max(dp[i][0][h],mx22);

            dp[i][1][h]=max(dp[i][1][h],mx11);
            dp[i][1][h]=max(dp[i][1][h],mx22);
            // sum+=val[i-1][h];
            // ll aux=0;
            // for(int nh=h+1;nh<=n;nh++)
            // {
            //     // aux+=val[i][nh];
            //     dp[i][h][0]=max(dp[i][h][0],dp[i-1][nh][0]);
            //     dp[i][h][0]=max(dp[i][h][0],dp[i-1][nh][1]);
                
            //     dp[i][h][1]=max(dp[i][h][1],dp[i-1][nh][0]);
            //     dp[i][h][1]=max(dp[i][h][1],dp[i-1][nh][1]+pre[i][nh]-pre[i][h]);

            // }
            // // ll og=sum;
            // for(int nh=0;nh<=h;nh++)
            // {
            //     // sum-=val[i-1][nh];
            //     dp[i][h][0]=max(dp[i][h][0],dp[i-1][nh][0]+pre[i-1][h]-pre[i-1][nh]);
            //     dp[i][h][0]=max(dp[i][h][0],dp[i-1][nh][1]);
                
            //     dp[i][h][1]=max(dp[i][h][1],dp[i-1][nh][0]+pre[i-1][j]-pre[i-1][nh]);
            //     dp[i][h][1]=max(dp[i][h][1],dp[i-1][nh][1]);
            // }
            // sum=og;
        }
    }
    for(int i=0;i<n;i++)
    {
        for(auto&ip:dp[i][0])
        {
            // cout<<"AT "<<ip.first<<' '<<i<<' '<<ip.second<<endl;
            ans=max(ans,ip.second);
        }
        for(auto&ip:dp[i][1])
        {
            // cout<<"AT1 "<<ip.first<<' '<<i<<' '<<ip.second<<endl;
            ans=max(ans,ip.second);
        }
    }
    return ans;
}
ll subtask2(ll&n,ll&m,vll&x,vll&y,vll&w)
{
    ll ans=0;
    ll val[2][n]={0};
    for(int i=0;i<2;i++)
    {
        for(int j=0;j<n;j++)
        {
            val[i][j]=0;
        }
    }
    ll sum1=0,sum0=0;
    for(int j=0;j<m;j++)
    {
        val[x[j]][y[j]]+=w[j];
        if(x[j]==1)
        {
            sum1+=w[j];
        }
        else
        {
            sum0+=w[j];
        }
    }
    ans=max(sum0,sum1);
    ll taken=0;
    ll cur=0;
    for(int j=0;j<n;j++)
    {
        cur+=val[0][j];
        taken+=val[1][j];
        ans=max(ans,cur);
        if(n>2)
            ans=max(ans,cur+sum1-taken);
    }
    return ans;
}
ll subtask3(ll&n,ll&m,vll&x,vll&y,vll&w)
{
    ll ans=0;
    ll val[n+1];
    for(int i=0;i<n;i++)val[i]=0;
    for(int j=0;j<m;j++)val[x[j]]+=w[j];
    ll dp[n+1][3][3];
    for(int i=0;i<n;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                dp[i][j][k]=0;
    for(int i=1;i<n;i++)
    {
        // wall not at i
        dp[i][0][0]=max(max(dp[i-1][0][0],dp[i-1][0][1]),dp[i-1][1][0]);
        dp[i][0][1]=max(max(dp[i-1][0][0],dp[i-1][0][1]),dp[i-1][1][0]+val[i]);

        dp[i][1][0]=max(max(dp[i-1][0][1],dp[i-1][0][0]+val[i-1]),dp[i-1][1][0]);
    }
    for(int i=0;i<n;i++)
    {
        ans=max({ans,dp[i][0][0],dp[i][0][1],dp[i][1][0],dp[i][1][1]});
    }
    return ans;
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,std::vector<int> W)
{
    ll n=N,m=M,ans=0;
    vector<ll> x(all(X)),y(all(Y)),w(all(W));
    ll mx_x=*max_element(all(x));
    // if(n<=3000)
        return solve(n,m,x,y,w);
    if(mx_x<=1)
        return subtask2(n,m,x,y,w);
    return subtask3(n,m,x,y,w);
}

Compilation message

fish.cpp: In function 'long long int solve(long long int&, long long int&, std::vector<long long int>&, std::vector<long long int>&, std::vector<long long int>&)':
fish.cpp:30:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |             while(pp<values[i].size() and values[i][pp].first<=j)
      |                   ~~^~~~~~~~~~~~~~~~~
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:181:16: warning: unused variable 'ans' [-Wunused-variable]
  181 |     ll n=N,m=M,ans=0;
      |                ^~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 85184 KB Output is correct
2 Correct 372 ms 97476 KB Output is correct
3 Correct 35 ms 45660 KB Output is correct
4 Correct 36 ms 45572 KB Output is correct
5 Execution timed out 1042 ms 199976 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23900 KB Output is correct
2 Correct 663 ms 111072 KB Output is correct
3 Correct 784 ms 124888 KB Output is correct
4 Correct 288 ms 85184 KB Output is correct
5 Correct 360 ms 97472 KB Output is correct
6 Correct 11 ms 23900 KB Output is correct
7 Correct 9 ms 23804 KB Output is correct
8 Correct 10 ms 23896 KB Output is correct
9 Correct 11 ms 23900 KB Output is correct
10 Correct 32 ms 45656 KB Output is correct
11 Correct 33 ms 45620 KB Output is correct
12 Correct 477 ms 101824 KB Output is correct
13 Correct 573 ms 117188 KB Output is correct
14 Correct 378 ms 93508 KB Output is correct
15 Correct 370 ms 83284 KB Output is correct
16 Correct 368 ms 93416 KB Output is correct
17 Correct 443 ms 101096 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 45656 KB Output is correct
2 Correct 34 ms 45660 KB Output is correct
3 Correct 79 ms 59732 KB Output is correct
4 Correct 63 ms 57888 KB Output is correct
5 Correct 123 ms 74764 KB Output is correct
6 Correct 111 ms 74840 KB Output is correct
7 Correct 108 ms 74768 KB Output is correct
8 Correct 110 ms 74832 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23896 KB Output is correct
2 Correct 11 ms 23900 KB Output is correct
3 Correct 10 ms 23900 KB Output is correct
4 Correct 10 ms 23900 KB Output is correct
5 Correct 12 ms 23916 KB Output is correct
6 Correct 11 ms 23900 KB Output is correct
7 Correct 9 ms 23900 KB Output is correct
8 Correct 9 ms 23900 KB Output is correct
9 Correct 12 ms 24012 KB Output is correct
10 Correct 13 ms 24668 KB Output is correct
11 Correct 10 ms 24156 KB Output is correct
12 Incorrect 14 ms 24516 KB 1st lines differ - on the 1st token, expected: '450122905247', found: '446815183025'
13 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23896 KB Output is correct
2 Correct 11 ms 23900 KB Output is correct
3 Correct 10 ms 23900 KB Output is correct
4 Correct 10 ms 23900 KB Output is correct
5 Correct 12 ms 23916 KB Output is correct
6 Correct 11 ms 23900 KB Output is correct
7 Correct 9 ms 23900 KB Output is correct
8 Correct 9 ms 23900 KB Output is correct
9 Correct 12 ms 24012 KB Output is correct
10 Correct 13 ms 24668 KB Output is correct
11 Correct 10 ms 24156 KB Output is correct
12 Incorrect 14 ms 24516 KB 1st lines differ - on the 1st token, expected: '450122905247', found: '446815183025'
13 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23896 KB Output is correct
2 Correct 11 ms 23900 KB Output is correct
3 Correct 10 ms 23900 KB Output is correct
4 Correct 10 ms 23900 KB Output is correct
5 Correct 12 ms 23916 KB Output is correct
6 Correct 11 ms 23900 KB Output is correct
7 Correct 9 ms 23900 KB Output is correct
8 Correct 9 ms 23900 KB Output is correct
9 Correct 12 ms 24012 KB Output is correct
10 Correct 13 ms 24668 KB Output is correct
11 Correct 10 ms 24156 KB Output is correct
12 Incorrect 14 ms 24516 KB 1st lines differ - on the 1st token, expected: '450122905247', found: '446815183025'
13 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 45656 KB Output is correct
2 Correct 34 ms 45660 KB Output is correct
3 Correct 79 ms 59732 KB Output is correct
4 Correct 63 ms 57888 KB Output is correct
5 Correct 123 ms 74764 KB Output is correct
6 Correct 111 ms 74840 KB Output is correct
7 Correct 108 ms 74768 KB Output is correct
8 Correct 110 ms 74832 KB Output is correct
9 Correct 215 ms 124980 KB Output is correct
10 Correct 90 ms 65104 KB Output is correct
11 Correct 189 ms 106320 KB Output is correct
12 Correct 10 ms 23900 KB Output is correct
13 Correct 10 ms 23900 KB Output is correct
14 Correct 11 ms 23900 KB Output is correct
15 Correct 13 ms 23920 KB Output is correct
16 Correct 11 ms 23900 KB Output is correct
17 Correct 9 ms 23864 KB Output is correct
18 Correct 33 ms 45752 KB Output is correct
19 Correct 33 ms 45808 KB Output is correct
20 Correct 39 ms 45596 KB Output is correct
21 Correct 32 ms 45660 KB Output is correct
22 Incorrect 212 ms 126976 KB 1st lines differ - on the 1st token, expected: '45561826463480', found: '44100552065661'
23 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 85184 KB Output is correct
2 Correct 372 ms 97476 KB Output is correct
3 Correct 35 ms 45660 KB Output is correct
4 Correct 36 ms 45572 KB Output is correct
5 Execution timed out 1042 ms 199976 KB Time limit exceeded
6 Halted 0 ms 0 KB -