oj.uz

Submission #1023963

# Submission time Handle Problem Language Result Execution time Memory
1023963 2024-07-15T10:14:08 Z Otalp Catfish Farm (IOI22_fish) C++17
15 / 100
 1000 ms 208064 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 = 500100;
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];
        }
        for(int i=0; i<=n; i++){
            d[i][0] += 0;
        }
        for(int i=0; i<=n; i++){
            for(auto h: d[i]){
                pos[i].pb(h.ff);
            }
        }
        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());
            int gls = 0;
            for(ll  h: pos[i]){
                ll j = h;
                pref[i][j] = pref[i][gls] + d[i][j];
                gls = 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]]);
                else dp[i][j] = max(dp[i][j], suf[dpos[ls]]-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<<pref[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];
    }
    return B::solve();
}

Compilation message

fish.cpp: In function 'long long int B::solve()':
fish.cpp:78: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]
   78 |                 while(ls + 1 < dpos.size() and dpos[ls + 1] <= j){
      |                       ~~~~~~~^~~~~~~~~~~~~
fish.cpp:80: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]
   80 |                     while(lls + 1 < pos[i-1].size() and pos[i-1][lls + 1] <= dpos[ls]) lls++;
      |                           ~~~~~~~~^~~~~~~~~~~~~~~~~
fish.cpp:83: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]
   83 |                 while(pls + 1 < pos[i].size() and pos[i][pls + 1] <= j) pls ++;
      |                       ~~~~~~~~^~~~~~~~~~~~~~~
fish.cpp:84: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]
   84 |                 while(dpls + 1 < pos[i-1].size() and pos[i-1][dpls + 1] <= j) dpls ++;
      |                       ~~~~~~~~~^~~~~~~~~~~~~~~~~
fish.cpp:95: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]
   95 |                 if(dpos.size() > ls + 1) dp[i][j] = max(dp[i][j], suf[dpos[ls + 1]]-pref[i][pos[i][pls]]);
      |                    ~~~~~~~~~~~~^~~~~~~~
fish.cpp:67:16: warning: unused variable 'pddp' [-Wunused-variable]
   67 |             ll pddp = -1e18, pdp = -1e18;
      |                ^~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 115848 KB Output is correct
2 Correct 371 ms 128340 KB Output is correct
3 Correct 139 ms 97964 KB Output is correct
4 Correct 138 ms 97968 KB Output is correct
5 Execution timed out 1032 ms 208064 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 44124 KB Output is correct
2 Correct 729 ms 154124 KB Output is correct
3 Correct 909 ms 177696 KB Output is correct
4 Correct 332 ms 117132 KB Output is correct
5 Correct 426 ms 128452 KB Output is correct
6 Correct 15 ms 44120 KB Output is correct
7 Correct 12 ms 44140 KB Output is correct
8 Correct 12 ms 44120 KB Output is correct
9 Correct 12 ms 44204 KB Output is correct
10 Correct 157 ms 98168 KB Output is correct
11 Correct 154 ms 97960 KB Output is correct
12 Correct 440 ms 132356 KB Output is correct
13 Correct 592 ms 147328 KB Output is correct
14 Correct 449 ms 124944 KB Output is correct
15 Correct 584 ms 134104 KB Output is correct
16 Correct 481 ms 124996 KB Output is correct
17 Correct 576 ms 133860 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 100952 KB Output is correct
2 Correct 168 ms 98096 KB Output is correct
3 Correct 201 ms 109264 KB Output is correct
4 Correct 310 ms 108864 KB Output is correct
5 Correct 310 ms 125108 KB Output is correct
6 Correct 272 ms 127412 KB Output is correct
7 Correct 277 ms 125184 KB Output is correct
8 Correct 278 ms 125108 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 44208 KB Output is correct
2 Correct 16 ms 44076 KB Output is correct
3 Correct 19 ms 46064 KB Output is correct
4 Correct 19 ms 44124 KB Output is correct
5 Correct 20 ms 42748 KB Output is correct
6 Correct 20 ms 42728 KB Output is correct
7 Correct 18 ms 44100 KB Output is correct
8 Correct 19 ms 46168 KB Output is correct
9 Correct 23 ms 44400 KB Output is correct
10 Correct 22 ms 46988 KB Output is correct
11 Incorrect 22 ms 44380 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '276017218506'
12 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 44208 KB Output is correct
2 Correct 16 ms 44076 KB Output is correct
3 Correct 19 ms 46064 KB Output is correct
4 Correct 19 ms 44124 KB Output is correct
5 Correct 20 ms 42748 KB Output is correct
6 Correct 20 ms 42728 KB Output is correct
7 Correct 18 ms 44100 KB Output is correct
8 Correct 19 ms 46168 KB Output is correct
9 Correct 23 ms 44400 KB Output is correct
10 Correct 22 ms 46988 KB Output is correct
11 Incorrect 22 ms 44380 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '276017218506'
12 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 44208 KB Output is correct
2 Correct 16 ms 44076 KB Output is correct
3 Correct 19 ms 46064 KB Output is correct
4 Correct 19 ms 44124 KB Output is correct
5 Correct 20 ms 42748 KB Output is correct
6 Correct 20 ms 42728 KB Output is correct
7 Correct 18 ms 44100 KB Output is correct
8 Correct 19 ms 46168 KB Output is correct
9 Correct 23 ms 44400 KB Output is correct
10 Correct 22 ms 46988 KB Output is correct
11 Incorrect 22 ms 44380 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '276017218506'
12 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 100952 KB Output is correct
2 Correct 168 ms 98096 KB Output is correct
3 Correct 201 ms 109264 KB Output is correct
4 Correct 310 ms 108864 KB Output is correct
5 Correct 310 ms 125108 KB Output is correct
6 Correct 272 ms 127412 KB Output is correct
7 Correct 277 ms 125184 KB Output is correct
8 Correct 278 ms 125108 KB Output is correct
9 Correct 301 ms 146456 KB Output is correct
10 Correct 180 ms 100172 KB Output is correct
11 Correct 444 ms 156640 KB Output is correct
12 Correct 18 ms 46128 KB Output is correct
13 Correct 19 ms 46200 KB Output is correct
14 Correct 20 ms 44636 KB Output is correct
15 Correct 18 ms 46172 KB Output is correct
16 Correct 16 ms 44124 KB Output is correct
17 Correct 20 ms 46064 KB Output is correct
18 Correct 179 ms 99500 KB Output is correct
19 Correct 171 ms 96544 KB Output is correct
20 Correct 182 ms 98188 KB Output is correct
21 Correct 174 ms 97960 KB Output is correct
22 Incorrect 337 ms 147100 KB 1st lines differ - on the 1st token, expected: '45561826463480', found: '44977339281292'
23 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 115848 KB Output is correct
2 Correct 371 ms 128340 KB Output is correct
3 Correct 139 ms 97964 KB Output is correct
4 Correct 138 ms 97968 KB Output is correct
5 Execution timed out 1032 ms 208064 KB Time limit exceeded
6 Halted 0 ms 0 KB -