oj.uz

Submission #1023907

# Submission time Handle Problem Language Result Execution time Memory
1023907 2024-07-15T09:23:46 Z Otalp Catfish Farm (IOI22_fish) C++17
9 / 100
 773 ms 161372 KB 
#include "fish.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second

const int MAXN = 300100;
int n, w[MAXN], m;
pii a[MAXN];

namespace B{
    map<int, ll> d[200100];
    map<int, ll> dp[200100];
    map<int, ll> pref[200100];
    map<int, ll> ddp[200100];
    vector<int> pos[200100];
    ll suf[200100];
    ll solve(){
        for(int i=1; i<=m; i++){
            d[a[i].ff][a[i].ss] += w[i];
            pos[a[i].ff].pb(a[i].ss);
        }
        d[0][0] = 1;
        pos[0].pb(0);
        for(int i=1; i<=n; i++){
            sort(pos[i].begin(), pos[i].end());
        }
        for(int i=1; i<=n; i++){
            dp[0][i] = -1e18;
            ddp[0][i] = -1e18;
        }
        dp[0][0] = 0;
        ddp[0][0] = 0;
        for(int i=1; i<=n; i++){
            //cout<<"_____________________\n";
            //cout<<i<<'\n';
            vector<int> alpos;
            for(auto h: pos[i-1]) alpos.pb(h);
            for(auto h: pos[i+1]) alpos.pb(h);
            sort(alpos.begin(), alpos.end());
            for(int  h: pos[i]){
                int j = h;
                pref[i][j] = pref[i][j - 1] + d[i][j];
            }
            vector<int> dpos;
            for(auto h: dp[i-1]){
                dpos.pb(h.ff);
            }
            ll mx = -1e18;
            int ls = pos[i].size()-1;
            for(int h = dpos.size()-1; h>=0; h--){
                int j = dpos[h];
                while(ls > 0 and pos[i][ls] > j) ls--;
                mx = max(mx, dp[i-1][j] + pref[i][j]);
                suf[j] = mx;
            }
            ll pddp = -1e18, pdp = -1e18;
            mx = -1e18;
            for(int h = dpos.size()-1; h>=0; h--){
                int j = dpos[h];
                mx = max(mx, dp[i-1][j]);
            }
            int pls=-1, dpls=-1;
            ls = -1;
            int lls = -1;
            for(int j: alpos){
                //cout<<j<<' ';
                while(ls + 1 < dpos.size() and dpos[ls + 1] <= j){
                    ls += 1;
                    while(lls + 1 < pos[i-1].size() and pos[i-1][lls + 1] <= dpos[ls]) lls++;
                    pdp = max(pdp, ddp[i-1][dpos[ls]]-pref[i-1][pos[i-1][lls]]);
                }
                while(pls + 1 < pos[i].size() and pos[i][pls + 1] <= j) pls ++;
                while(dpls + 1 < pos[i-1].size() and pos[i-1][dpls + 1] <= j) dpls ++;
                ddp[i][j] = mx;
                dp[i][j] = 0;
                //if(dpls < 0){
                //    cout<<"asdas\n";
                //    cout<<j<<'\n';
                //    cout<<dpls+1<<'\n';
                //    continue;
                //}
                ddp[i][j] = max(ddp[i][j], pdp + pref[i-1][pos[i-1][dpls]]);
                dp[i][j] = ddp[i][j];
                if(dpos.size() > ls + 1) dp[i][j] = max(dp[i][j], suf[dpos[ls + 1]]-pref[i][pos[i][pls]]);
                dp[i][j] = max(dp[i][j], pdp+pref[i-1][pos[i-1][dpls]]);
            }
            //cout<<'\n';
        }
        //for(int i=1; i<=n; i++){
        //    for(int j=0; j<=n; j++){
        //        cout<<dp[i][j]<<' ';
        //    }
        //    cout<<'\n';
        //}
        ll ans = 0;
        for(int i=0; i<=n; i++) ans = max(ans, dp[n][i]);
        return ans;
    }
}




long long max_weights(int N, int M, vector<int> X, vector<int> Y,
                      vector<int> W) {
    
    n = N;
    m = M;
    for(int i=1; i<=m; i++){
        a[i] = {X[i-1]+1, Y[i-1]+1};
    }
    for(int i=1; i<=m; i++){
        w[i] = W[i-1];
    }
    for(int i=1; i<=n; i++){
        a[i + m] = {i, 0};
        w[i+m] = 0;
    }
    m += n;
    return B::solve();
}

Compilation message

fish.cpp: In function 'long long int B::solve()':
fish.cpp:71:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |                 while(ls + 1 < dpos.size() and dpos[ls + 1] <= j){
      |                       ~~~~~~~^~~~~~~~~~~~~
fish.cpp:73:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |                     while(lls + 1 < pos[i-1].size() and pos[i-1][lls + 1] <= dpos[ls]) lls++;
      |                           ~~~~~~~~^~~~~~~~~~~~~~~~~
fish.cpp:76:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |                 while(pls + 1 < pos[i].size() and pos[i][pls + 1] <= j) pls ++;
      |                       ~~~~~~~~^~~~~~~~~~~~~~~
fish.cpp:77:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |                 while(dpls + 1 < pos[i-1].size() and pos[i-1][dpls + 1] <= j) dpls ++;
      |                       ~~~~~~~~~^~~~~~~~~~~~~~~~~
fish.cpp:88:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   88 |                 if(dpos.size() > ls + 1) dp[i][j] = max(dp[i][j], suf[dpos[ls + 1]]-pref[i][pos[i][pls]]);
      |                    ~~~~~~~~~~~~^~~~~~~~
fish.cpp:60:16: warning: unused variable 'pddp' [-Wunused-variable]
   60 |             ll pddp = -1e18, pdp = -1e18;
      |                ^~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 327 ms 121324 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '36638591909'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 42588 KB Output is correct
2 Incorrect 773 ms 160592 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '84649862111'
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 103992 KB Output is correct
2 Correct 159 ms 104088 KB Output is correct
3 Correct 198 ms 114280 KB Output is correct
4 Correct 200 ms 115268 KB Output is correct
5 Correct 263 ms 132528 KB Output is correct
6 Correct 249 ms 132672 KB Output is correct
7 Correct 254 ms 132716 KB Output is correct
8 Correct 257 ms 132560 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 42588 KB Output is correct
2 Correct 19 ms 42584 KB Output is correct
3 Correct 19 ms 42584 KB Output is correct
4 Correct 18 ms 42588 KB Output is correct
5 Correct 19 ms 42588 KB Output is correct
6 Correct 21 ms 42756 KB Output is correct
7 Correct 20 ms 42704 KB Output is correct
8 Correct 19 ms 42584 KB Output is correct
9 Correct 19 ms 42868 KB Output is correct
10 Correct 23 ms 43612 KB Output is correct
11 Incorrect 20 ms 43100 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '209821364205'
12 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 42588 KB Output is correct
2 Correct 19 ms 42584 KB Output is correct
3 Correct 19 ms 42584 KB Output is correct
4 Correct 18 ms 42588 KB Output is correct
5 Correct 19 ms 42588 KB Output is correct
6 Correct 21 ms 42756 KB Output is correct
7 Correct 20 ms 42704 KB Output is correct
8 Correct 19 ms 42584 KB Output is correct
9 Correct 19 ms 42868 KB Output is correct
10 Correct 23 ms 43612 KB Output is correct
11 Incorrect 20 ms 43100 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '209821364205'
12 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 42588 KB Output is correct
2 Correct 19 ms 42584 KB Output is correct
3 Correct 19 ms 42584 KB Output is correct
4 Correct 18 ms 42588 KB Output is correct
5 Correct 19 ms 42588 KB Output is correct
6 Correct 21 ms 42756 KB Output is correct
7 Correct 20 ms 42704 KB Output is correct
8 Correct 19 ms 42584 KB Output is correct
9 Correct 19 ms 42868 KB Output is correct
10 Correct 23 ms 43612 KB Output is correct
11 Incorrect 20 ms 43100 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '209821364205'
12 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 103992 KB Output is correct
2 Correct 159 ms 104088 KB Output is correct
3 Correct 198 ms 114280 KB Output is correct
4 Correct 200 ms 115268 KB Output is correct
5 Correct 263 ms 132528 KB Output is correct
6 Correct 249 ms 132672 KB Output is correct
7 Correct 254 ms 132716 KB Output is correct
8 Correct 257 ms 132560 KB Output is correct
9 Correct 328 ms 157716 KB Output is correct
10 Correct 185 ms 101892 KB Output is correct
11 Correct 387 ms 161372 KB Output is correct
12 Correct 19 ms 42584 KB Output is correct
13 Correct 19 ms 42588 KB Output is correct
14 Correct 19 ms 42664 KB Output is correct
15 Correct 18 ms 42588 KB Output is correct
16 Correct 24 ms 42588 KB Output is correct
17 Correct 19 ms 42588 KB Output is correct
18 Correct 170 ms 103992 KB Output is correct
19 Correct 156 ms 104100 KB Output is correct
20 Correct 162 ms 103992 KB Output is correct
21 Correct 156 ms 103992 KB Output is correct
22 Incorrect 344 ms 157572 KB 1st lines differ - on the 1st token, expected: '45561826463480', found: '35041184705483'
23 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 327 ms 121324 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '36638591909'
2 Halted 0 ms 0 KB -