oj.uz

Submission #1023908

# Submission time Handle Problem Language Result Execution time Memory
1023908 2024-07-15T09:25:17 Z Otalp Catfish Farm (IOI22_fish) C++17
9 / 100
 836 ms 165812 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<ll, ll> d[200100];
    map<ll, ll> dp[200100];
    map<ll, ll> pref[200100];
    map<ll, ll> ddp[200100];
    vector<ll> pos[200100];
    ll suf[200100];
    ll solve(){
        for(ll 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(ll i=1; i<=n; i++){
            sort(pos[i].begin(), pos[i].end());
        }
        for(ll i=1; i<=n; i++){
            dp[0][i] = -1e18;
            ddp[0][i] = -1e18;
        }
        dp[0][0] = 0;
        ddp[0][0] = 0;
        for(ll i=1; i<=n; i++){
            //cout<<"_____________________\n";
            //cout<<i<<'\n';
            vector<ll> 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(ll  h: pos[i]){
                ll j = h;
                pref[i][j] = pref[i][j - 1] + d[i][j];
            }
            vector<ll> dpos;
            for(auto h: dp[i-1]){
                dpos.pb(h.ff);
            }
            ll mx = -1e18;
            ll ls = pos[i].size()-1;
            for(ll h = dpos.size()-1; h>=0; h--){
                ll 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(ll h = dpos.size()-1; h>=0; h--){
                ll j = dpos[h];
                mx = max(mx, dp[i-1][j]);
            }
            ll pls=-1, dpls=-1;
            ls = -1;
            ll lls = -1;
            for(ll 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(ll i=1; i<=n; i++){
        //    for(ll j=0; j<=n; j++){
        //        cout<<dp[i][j]<<' ';
        //    }
        //    cout<<'\n';
        //}
        ll ans = 0;
        for(ll 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: 'long long int' and 'std::vector<long long 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: 'long long int' and 'std::vector<long long 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: 'long long int' and 'std::vector<long long 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: 'long long int' and 'std::vector<long long 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<long long int>::size_type' {aka 'long unsigned int'} and 'long long 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 357 ms 121532 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 42584 KB Output is correct
2 Incorrect 836 ms 161116 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 174 ms 104108 KB Output is correct
2 Correct 174 ms 104100 KB Output is correct
3 Correct 212 ms 114136 KB Output is correct
4 Correct 210 ms 115128 KB Output is correct
5 Correct 285 ms 132532 KB Output is correct
6 Correct 287 ms 132528 KB Output is correct
7 Correct 306 ms 132576 KB Output is correct
8 Correct 307 ms 132844 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 42588 KB Output is correct
2 Correct 21 ms 42584 KB Output is correct
3 Correct 20 ms 42624 KB Output is correct
4 Correct 20 ms 42588 KB Output is correct
5 Correct 20 ms 42584 KB Output is correct
6 Correct 21 ms 42584 KB Output is correct
7 Correct 21 ms 42588 KB Output is correct
8 Correct 28 ms 42588 KB Output is correct
9 Correct 26 ms 42964 KB Output is correct
10 Correct 22 ms 43572 KB Output is correct
11 Incorrect 22 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 20 ms 42588 KB Output is correct
2 Correct 21 ms 42584 KB Output is correct
3 Correct 20 ms 42624 KB Output is correct
4 Correct 20 ms 42588 KB Output is correct
5 Correct 20 ms 42584 KB Output is correct
6 Correct 21 ms 42584 KB Output is correct
7 Correct 21 ms 42588 KB Output is correct
8 Correct 28 ms 42588 KB Output is correct
9 Correct 26 ms 42964 KB Output is correct
10 Correct 22 ms 43572 KB Output is correct
11 Incorrect 22 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 20 ms 42588 KB Output is correct
2 Correct 21 ms 42584 KB Output is correct
3 Correct 20 ms 42624 KB Output is correct
4 Correct 20 ms 42588 KB Output is correct
5 Correct 20 ms 42584 KB Output is correct
6 Correct 21 ms 42584 KB Output is correct
7 Correct 21 ms 42588 KB Output is correct
8 Correct 28 ms 42588 KB Output is correct
9 Correct 26 ms 42964 KB Output is correct
10 Correct 22 ms 43572 KB Output is correct
11 Incorrect 22 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 174 ms 104108 KB Output is correct
2 Correct 174 ms 104100 KB Output is correct
3 Correct 212 ms 114136 KB Output is correct
4 Correct 210 ms 115128 KB Output is correct
5 Correct 285 ms 132532 KB Output is correct
6 Correct 287 ms 132528 KB Output is correct
7 Correct 306 ms 132576 KB Output is correct
8 Correct 307 ms 132844 KB Output is correct
9 Correct 351 ms 157632 KB Output is correct
10 Correct 194 ms 104172 KB Output is correct
11 Correct 403 ms 165812 KB Output is correct
12 Correct 20 ms 42584 KB Output is correct
13 Correct 21 ms 42588 KB Output is correct
14 Correct 20 ms 42588 KB Output is correct
15 Correct 20 ms 42588 KB Output is correct
16 Correct 20 ms 42588 KB Output is correct
17 Correct 20 ms 42584 KB Output is correct
18 Correct 193 ms 103936 KB Output is correct
19 Correct 175 ms 104104 KB Output is correct
20 Correct 177 ms 103992 KB Output is correct
21 Correct 175 ms 104100 KB Output is correct
22 Incorrect 373 ms 158140 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 357 ms 121532 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '36638591909'
2 Halted 0 ms 0 KB -