oj.uz

Submission #1075582

# Submission time Handle Problem Language Result Execution time Memory
1075582 2024-08-26T07:50:11 Z Faisal_Saqib Catfish Farm (IOI22_fish) C++17
81 / 100
 1000 ms 259664 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);
        possible[i].push_back(n);
        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:32: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]
   32 |             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:183:16: warning: unused variable 'ans' [-Wunused-variable]
  183 |     ll n=N,m=M,ans=0;
      |                ^~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 102048 KB Output is correct
2 Correct 435 ms 116120 KB Output is correct
3 Correct 60 ms 64572 KB Output is correct
4 Correct 57 ms 64596 KB Output is correct
5 Execution timed out 1076 ms 214360 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23900 KB Output is correct
2 Correct 747 ms 128108 KB Output is correct
3 Correct 846 ms 143492 KB Output is correct
4 Correct 343 ms 102060 KB Output is correct
5 Correct 419 ms 116160 KB Output is correct
6 Correct 11 ms 23896 KB Output is correct
7 Correct 11 ms 23900 KB Output is correct
8 Correct 10 ms 23724 KB Output is correct
9 Correct 10 ms 23896 KB Output is correct
10 Correct 62 ms 64596 KB Output is correct
11 Correct 55 ms 64592 KB Output is correct
12 Correct 520 ms 118576 KB Output is correct
13 Correct 648 ms 135916 KB Output is correct
14 Correct 459 ms 110316 KB Output is correct
15 Correct 414 ms 102232 KB Output is correct
16 Correct 423 ms 110348 KB Output is correct
17 Correct 499 ms 119748 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 64596 KB Output is correct
2 Correct 59 ms 64504 KB Output is correct
3 Correct 103 ms 78428 KB Output is correct
4 Correct 95 ms 77648 KB Output is correct
5 Correct 150 ms 97224 KB Output is correct
6 Correct 142 ms 97208 KB Output is correct
7 Correct 139 ms 97108 KB Output is correct
8 Correct 151 ms 97040 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23900 KB Output is correct
2 Correct 11 ms 23900 KB Output is correct
3 Correct 12 ms 23744 KB Output is correct
4 Correct 12 ms 23900 KB Output is correct
5 Correct 10 ms 23900 KB Output is correct
6 Correct 10 ms 23896 KB Output is correct
7 Correct 12 ms 23900 KB Output is correct
8 Correct 11 ms 23900 KB Output is correct
9 Correct 11 ms 23976 KB Output is correct
10 Correct 13 ms 24668 KB Output is correct
11 Correct 12 ms 24156 KB Output is correct
12 Correct 14 ms 24572 KB Output is correct
13 Correct 11 ms 23900 KB Output is correct
14 Correct 11 ms 24408 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23900 KB Output is correct
2 Correct 11 ms 23900 KB Output is correct
3 Correct 12 ms 23744 KB Output is correct
4 Correct 12 ms 23900 KB Output is correct
5 Correct 10 ms 23900 KB Output is correct
6 Correct 10 ms 23896 KB Output is correct
7 Correct 12 ms 23900 KB Output is correct
8 Correct 11 ms 23900 KB Output is correct
9 Correct 11 ms 23976 KB Output is correct
10 Correct 13 ms 24668 KB Output is correct
11 Correct 12 ms 24156 KB Output is correct
12 Correct 14 ms 24572 KB Output is correct
13 Correct 11 ms 23900 KB Output is correct
14 Correct 11 ms 24408 KB Output is correct
15 Correct 12 ms 24152 KB Output is correct
16 Correct 15 ms 24668 KB Output is correct
17 Correct 80 ms 40192 KB Output is correct
18 Correct 71 ms 38504 KB Output is correct
19 Correct 72 ms 38996 KB Output is correct
20 Correct 61 ms 37200 KB Output is correct
21 Correct 61 ms 36948 KB Output is correct
22 Correct 126 ms 49744 KB Output is correct
23 Correct 29 ms 30300 KB Output is correct
24 Correct 85 ms 39852 KB Output is correct
25 Correct 12 ms 24664 KB Output is correct
26 Correct 26 ms 29028 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23900 KB Output is correct
2 Correct 11 ms 23900 KB Output is correct
3 Correct 12 ms 23744 KB Output is correct
4 Correct 12 ms 23900 KB Output is correct
5 Correct 10 ms 23900 KB Output is correct
6 Correct 10 ms 23896 KB Output is correct
7 Correct 12 ms 23900 KB Output is correct
8 Correct 11 ms 23900 KB Output is correct
9 Correct 11 ms 23976 KB Output is correct
10 Correct 13 ms 24668 KB Output is correct
11 Correct 12 ms 24156 KB Output is correct
12 Correct 14 ms 24572 KB Output is correct
13 Correct 11 ms 23900 KB Output is correct
14 Correct 11 ms 24408 KB Output is correct
15 Correct 12 ms 24152 KB Output is correct
16 Correct 15 ms 24668 KB Output is correct
17 Correct 80 ms 40192 KB Output is correct
18 Correct 71 ms 38504 KB Output is correct
19 Correct 72 ms 38996 KB Output is correct
20 Correct 61 ms 37200 KB Output is correct
21 Correct 61 ms 36948 KB Output is correct
22 Correct 126 ms 49744 KB Output is correct
23 Correct 29 ms 30300 KB Output is correct
24 Correct 85 ms 39852 KB Output is correct
25 Correct 12 ms 24664 KB Output is correct
26 Correct 26 ms 29028 KB Output is correct
27 Correct 15 ms 27484 KB Output is correct
28 Correct 400 ms 96588 KB Output is correct
29 Correct 728 ms 155172 KB Output is correct
30 Correct 869 ms 253588 KB Output is correct
31 Correct 792 ms 250388 KB Output is correct
32 Correct 482 ms 115796 KB Output is correct
33 Correct 801 ms 259664 KB Output is correct
34 Correct 889 ms 259624 KB Output is correct
35 Correct 217 ms 91220 KB Output is correct
36 Correct 786 ms 216144 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 64596 KB Output is correct
2 Correct 59 ms 64504 KB Output is correct
3 Correct 103 ms 78428 KB Output is correct
4 Correct 95 ms 77648 KB Output is correct
5 Correct 150 ms 97224 KB Output is correct
6 Correct 142 ms 97208 KB Output is correct
7 Correct 139 ms 97108 KB Output is correct
8 Correct 151 ms 97040 KB Output is correct
9 Correct 249 ms 147280 KB Output is correct
10 Correct 109 ms 72720 KB Output is correct
11 Correct 234 ms 121428 KB Output is correct
12 Correct 13 ms 24152 KB Output is correct
13 Correct 11 ms 23900 KB Output is correct
14 Correct 11 ms 23900 KB Output is correct
15 Correct 10 ms 23896 KB Output is correct
16 Correct 10 ms 23896 KB Output is correct
17 Correct 13 ms 23900 KB Output is correct
18 Correct 62 ms 64364 KB Output is correct
19 Correct 60 ms 64600 KB Output is correct
20 Correct 63 ms 64420 KB Output is correct
21 Correct 61 ms 64592 KB Output is correct
22 Correct 291 ms 144908 KB Output is correct
23 Correct 313 ms 166736 KB Output is correct
24 Correct 350 ms 175700 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 102048 KB Output is correct
2 Correct 435 ms 116120 KB Output is correct
3 Correct 60 ms 64572 KB Output is correct
4 Correct 57 ms 64596 KB Output is correct
5 Execution timed out 1076 ms 214360 KB Time limit exceeded
6 Halted 0 ms 0 KB -