oj.uz

Submission #1067040

# Submission time Handle Problem Language Result Execution time Memory
1067040 2024-08-20T10:01:56 Z epicci23 Catfish Farm (IOI22_fish) C++17
9 / 100
 450 ms 76748 KB 
#include "bits/stdc++.h"
#include "fish.h"
//#define int64_t long long
#define all(v) v.begin() , v.end()
#define sz(a) (int64_t)a.size()
using namespace std;

const int64_t INF = 1e15;

long long max_weights(int N, int M, vector<int> X, vector<int> Y,vector<int> W){
  int64_t n,m,ans=0;
  n=N,m=M;
  vector<array<int64_t,3>> ar(m);
  for(int64_t i=0;i<m;i++){
    ar[i][0]=X[i];
    ar[i][1]=Y[i];
    ar[i][2]=W[i];
    ar[i][0]++;
  }
  vector<int64_t> consider[n+5];
  vector<array<int64_t,2>> pre[n+5];
  vector<array<int64_t,2>> fish[n+5];

  for(int64_t i=0;i<m;i++){
    if(ar[i][0]>1) consider[ar[i][0]-1].push_back(ar[i][1]);
    if(ar[i][0]+1<=n) consider[ar[i][0]+1].push_back(ar[i][1]);
  }

  for(int64_t i=0;i<=n;i++){
    consider[i].push_back(0);
    sort(all(consider[i]));
    consider[i].erase(unique(all(consider[i])),consider[i].end());
  }

  for(int64_t i=0;i<m;i++) fish[ar[i][0]].push_back({ar[i][1],ar[i][2]});
  for(int64_t i=1;i<=n;i++){
    fish[i].push_back({0,0});
    sort(all(fish[i]));
    int64_t cur=0;
    for(auto x:fish[i]){
      cur+=x[1];
      pre[i].push_back({x[0],cur});
    }
  }

  vector<int64_t> dp[n+5][2];
  for(int64_t i=0;i<=n;i++){
    dp[i][0].assign(sz(consider[i]),0);
    dp[i][1].assign(sz(consider[i]),0);
  }

  auto get_sum=[&](int64_t i,int64_t j)->int64_t{
   if(i<1 || i>n) return 0;
   array<int64_t,2> bs={j+1,-1};
   int64_t it=lower_bound(all(pre[i]),bs)-pre[i].begin();
   if(it>0) return pre[i][it-1][1];
   return 0;
  };

  for(int64_t i=1;i<=n;i++){
    // calc increasing dp
    vector<array<int64_t,2>> v;
    int64_t cur=0;
    for(int64_t j=0;j<sz(dp[i-1][0]);j++){
      cur=max(cur,dp[i-1][0][j]-get_sum(i-1,consider[i-1][j]));
      v.push_back({consider[i-1][j],cur});
    }

    auto get_val=[&](int64_t u,int64_t t)->int64_t{
      array<int64_t,2> bs={u+1,-1};
      int64_t it=lower_bound(all(v),bs)-v.begin();
      if(it-t>=0 && it-t<sz(v)) return v[it-t][1];
      return -INF;
    };
    
    for(int64_t j=0;j<sz(consider[i]);j++){
      int64_t u=consider[i][j];
      int64_t val=get_sum(i-1,u)+get_val(u,1);
      dp[i][0][j]=max(dp[i][0][j],val);
    }

    // calc decrasing dp

    v.clear();
    cur=0;
    for(int64_t j=sz(dp[i-1][1])-1;j>=0;j--){
      cur=max(cur,dp[i-1][1][j]);
      v.push_back({consider[i-1][j],cur});
    }
    reverse(all(v));

    for(int64_t j=0;j<sz(dp[i][1]);j++){
      int64_t u=consider[i][j];
      dp[i][1][j]=max(dp[i][1][j],get_val(u,0)-get_sum(i,u)+get_sum(i+1,u));
    }
    
    if(i>=2){ // new block
      vector<array<int64_t,2>> arka[2];
      cur=0;
      for(int64_t j=0;j<sz(consider[i-2]);j++){
        int64_t u=consider[i-2][j];
        cur=max(cur,dp[i-2][0][j]);
        cur=max(cur,dp[i-2][1][j]-get_sum(i-1,u));
        arka[0].push_back({u,cur});
      }
      cur=0;
      for(int64_t j=sz(consider[i-2])-1;j>=0;j--){
        int64_t u=consider[i-2][j];
        cur=max(cur,dp[i-2][0][j]+get_sum(i-1,u));
        cur=max(cur,dp[i-2][1][j]);
        arka[1].push_back({u,cur});
      }
      reverse(all(arka[1]));

      auto get_kucuk=[&](int64_t u)->int64_t{
        array<int64_t,2> bs={u+1,-1};
        int64_t it=lower_bound(all(arka[0]),bs)-arka[0].begin();
        if(it>0) return arka[0][it-1][1];
        return -INF;
      };

      auto get_buyuk=[&](int64_t u)->int64_t{
        array<int64_t,2> bs={u+1,-1};
        int64_t it=lower_bound(all(arka[1]),bs)-arka[1].begin();
        if(it<sz(arka[1])) return arka[1][it][1];
        return -INF;
      };

      for(int64_t j=0;j<sz(consider[i]);j++){
        int64_t u=consider[i][j];
        dp[i][0][j]=max(dp[i][0][j],get_buyuk(u));
        dp[i][0][j]=max(dp[i][0][j],get_kucuk(u)+get_sum(i-1,u));
      }

      for(int64_t j=0;j<sz(consider[i]);j++){
        int64_t u=consider[i][j];
        dp[i][1][j]=max(dp[i][1][j],get_buyuk(u)+get_sum(i+1,u));
        dp[i][1][j]=max(dp[i][1][j],get_kucuk(u)+get_sum(i+1,u)+get_sum(i-1,u));
      }
    }

    // inc to dec

    v.clear();
    cur=0;
    //cout << "kur: " << '\n';
    for(int64_t j=sz(consider[i-1])-1;j>=0;j--){
      int64_t u=consider[i-1][j];
      //cout << i << ' ' << j << ' ' << dp[i-1][0][j] << ' ' << get_sum(i,u) << '\n';
      cur=max(cur,dp[i-1][0][j]+get_sum(i,u));
      v.push_back({u,cur});
    }
    reverse(all(v));

    for(int64_t j=0;j<sz(consider[i]);j++){
      int64_t u=consider[i][j];
      dp[i][1][j]=max(dp[i][1][j],get_val(u,0)-get_sum(i,u)+get_sum(i+1,u));
      //cout << "hmm: " << i << ' ' << j << ' ' << u << '\n';
      //cout << get_val(u,0) << ' ' << get_sum(i,u) << ' ' << get_sum(i+1,u) << '\n';
      //cout << dp[i][1][j] << '\n';
    }
   
    for(int64_t j=0;j<sz(consider[i]);j++){
      //cout << "check: " << i << ' ' << j << ' ' << consider[i][j] << '\n';
      //cout << dp[i][0][j] << ' ' << dp[i][1][j] << '\n';
      ans=max(ans,dp[i][0][j]+get_sum(i+1,consider[i][j]));
      ans=max(ans,dp[i][1][j]);
    }
  }
  return ans;
}


/*void _(){
  int64_t n,m,ans=0;
  cin >> n >> m;
  vector<array<int64_t,3>> ar(m);
  for(int64_t i=0;i<m;i++){
    cin >> ar[i][0] >> ar[i][1] >> ar[i][2];
    ar[i][0]++;
  }
  vector<int64_t> consider[n+5];
  vector<array<int64_t,2>> pre[n+5];
  vector<array<int64_t,2>> fish[n+5];

  for(int64_t i=0;i<m;i++){
    if(ar[i][0]>1) consider[ar[i][0]-1].push_back(ar[i][1]);
    if(ar[i][0]+1<=n) consider[ar[i][0]+1].push_back(ar[i][1]);
  }

  for(int64_t i=0;i<=n;i++){
    consider[i].push_back(0);
    sort(all(consider[i]));
    consider[i].erase(unique(all(consider[i])),consider[i].end());
  }

  for(int64_t i=0;i<m;i++) fish[ar[i][0]].push_back({ar[i][1],ar[i][2]});
  for(int64_t i=1;i<=n;i++){
    fish[i].push_back({0,0});
    sort(all(fish[i]));
    int64_t cur=0;
    for(auto x:fish[i]){
      cur+=x[1];
      pre[i].push_back({x[0],cur});
    }
  }

  vector<int64_t> dp[n+5][2];
  for(int64_t i=0;i<=n;i++){
    dp[i][0].assign(sz(consider[i]),0);
    dp[i][1].assign(sz(consider[i]),0);
  }

  auto get_sum=[&](int64_t i,int64_t j)->int64_t{
   if(i<1 || i>n) return 0;
   array<int64_t,2> bs={j+1,-1};
   int64_t it=lower_bound(all(pre[i]),bs)-pre[i].begin();
   if(it>0) return pre[i][it-1][1];
   return 0;
  };

  for(int64_t i=1;i<=n;i++){
    // calc increasing dp
    vector<array<int64_t,2>> v;
    int64_t cur=0;
    for(int64_t j=0;j<sz(dp[i-1][0]);j++){
      cur=max(cur,dp[i-1][0][j]-get_sum(i-1,consider[i-1][j]));
      v.push_back({consider[i-1][j],cur});
    }

    auto get_val=[&](int64_t u,int64_t t)->int64_t{
      array<int64_t,2> bs={u+1,-1};
      int64_t it=lower_bound(all(v),bs)-v.begin();
      if(it-t>=0 && it-t<sz(v)) return v[it-t][1];
      return -INF;
    };
    
    for(int64_t j=0;j<sz(consider[i]);j++){
      int64_t u=consider[i][j];
      int64_t val=get_sum(i-1,u)+get_val(u,1);
      dp[i][0][j]=max(dp[i][0][j],val);
      //cout << "hm0: " << i << ' ' << j << ' ' << u << '\n';
      //cout << dp[i][0][j] << '\n';
    }

    // calc decrasing dp

    v.clear();
    cur=0;
    for(int64_t j=sz(dp[i-1][1])-1;j>=0;j--){
      cur=max(cur,dp[i-1][1][j]);
      v.push_back({consider[i-1][j],cur});
    }
    reverse(all(v));

    for(int64_t j=0;j<sz(dp[i][1]);j++){
      int64_t u=consider[i][j];
      dp[i][1][j]=max(dp[i][1][j],get_val(u,0)-get_sum(i,u)+get_sum(i+1,u));
      //cout << "hm1: " << i << ' ' << j << ' ' << u << '\n';
      //cout << dp[i][1][j] << '\n';
    }
    
    if(i>=2){ // new block
      vector<array<int64_t,2>> arka[2];
      cur=0;
      for(int64_t j=0;j<sz(consider[i-2]);j++){
        int64_t u=consider[i-2][j];
        cur=max(cur,dp[i-2][0][j]);
        cur=max(cur,dp[i-2][1][j]-get_sum(i-1,u));
        arka[0].push_back({u,cur});
      }
      cur=0;
      for(int64_t j=sz(consider[i-2])-1;j>=0;j--){
        int64_t u=consider[i-2][j];
        cur=max(cur,dp[i-2][0][j]+get_sum(i-1,u));
        cur=max(cur,dp[i-2][1][j]);
        arka[1].push_back({u,cur});
      }
      reverse(all(arka[1]));

      auto get_kucuk=[&](int64_t u)->int64_t{
        array<int64_t,2> bs={u+1,-1};
        int64_t it=lower_bound(all(arka[0]),bs)-arka[0].begin();
        if(it>0) return arka[0][it-1][1];
        return -INF;
      };

      auto get_buyuk=[&](int64_t u)->int64_t{
        array<int64_t,2> bs={u+1,-1};
        int64_t it=lower_bound(all(arka[1]),bs)-arka[1].begin();
        if(it<sz(arka[1])) return arka[1][it][1];
        return -INF;
      };

      for(int64_t j=0;j<sz(consider[i]);j++){
        int64_t u=consider[i][j];
        dp[i][0][j]=max(dp[i][0][j],get_buyuk(u));
        dp[i][0][j]=max(dp[i][0][j],get_kucuk(u)+get_sum(i-1,u));
        //cout << "b0: " << i << ' ' << j << ' ' << u << '\n';
        //cout << dp[i][0][j] << '\n';
      }

      for(int64_t j=0;j<sz(consider[i]);j++){
        int64_t u=consider[i][j];
        dp[i][1][j]=max(dp[i][1][j],get_buyuk(u)+get_sum(i+1,u));
        dp[i][1][j]=max(dp[i][1][j],get_kucuk(u)+get_sum(i+1,u)+get_sum(i-1,u));
        //cout << "b1: " << i << ' ' << j << ' ' << u << '\n';
        //cout << dp[i][1][j] << '\n';
      }
    }

    // inc to dec

    v.clear();
    cur=0;
    //cout << "kur: " << '\n';
    for(int64_t j=sz(consider[i-1])-1;j>=0;j--){
      int64_t u=consider[i-1][j];
      //cout << i << ' ' << j << ' ' << dp[i-1][0][j] << ' ' << get_sum(i,u) << '\n';
      cur=max(cur,dp[i-1][0][j]+get_sum(i,u));
      v.push_back({u,cur});
    }
    reverse(all(v));

    for(int64_t j=0;j<sz(consider[i]);j++){
      int64_t u=consider[i][j];
      dp[i][1][j]=max(dp[i][1][j],get_val(u,0)-get_sum(i,u)+get_sum(i+1,u));
      //cout << "hmm: " << i << ' ' << j << ' ' << u << '\n';
      //cout << get_val(u,0) << ' ' << get_sum(i,u) << ' ' << get_sum(i+1,u) << '\n';
      //cout << dp[i][1][j] << '\n';
    }
   
    for(int64_t j=0;j<sz(consider[i]);j++){
      //cout << "check: " << i << ' ' << j << ' ' << consider[i][j] << '\n';
      //cout << dp[i][0][j] << ' ' << dp[i][1][j] << '\n';
      ans=max(ans,dp[i][0][j]+get_sum(i+1,consider[i][j]));
      ans=max(ans,dp[i][1][j]);
    }
  }
  cout << ans << '\n';
}

int64_t32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int64_t tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}*/

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 39252 KB Output is correct
2 Correct 110 ms 44840 KB Output is correct
3 Correct 45 ms 27744 KB Output is correct
4 Correct 52 ms 27740 KB Output is correct
5 Correct 450 ms 76748 KB Output is correct
6 Correct 328 ms 76368 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 233 ms 52132 KB Output is correct
3 Correct 283 ms 60788 KB Output is correct
4 Correct 91 ms 39256 KB Output is correct
5 Correct 116 ms 44948 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 43 ms 27732 KB Output is correct
11 Correct 47 ms 27740 KB Output is correct
12 Correct 141 ms 41052 KB Output is correct
13 Correct 166 ms 47292 KB Output is correct
14 Correct 122 ms 38656 KB Output is correct
15 Correct 151 ms 42816 KB Output is correct
16 Correct 121 ms 38532 KB Output is correct
17 Correct 136 ms 42664 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 27804 KB Output is correct
2 Correct 45 ms 27740 KB Output is correct
3 Incorrect 60 ms 30800 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '16359027219341'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 692 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 1 ms 348 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '199904465818'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 692 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 1 ms 348 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '199904465818'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 692 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 1 ms 348 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '199904465818'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 27804 KB Output is correct
2 Correct 45 ms 27740 KB Output is correct
3 Incorrect 60 ms 30800 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '16359027219341'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 39252 KB Output is correct
2 Correct 110 ms 44840 KB Output is correct
3 Correct 45 ms 27744 KB Output is correct
4 Correct 52 ms 27740 KB Output is correct
5 Correct 450 ms 76748 KB Output is correct
6 Correct 328 ms 76368 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 233 ms 52132 KB Output is correct
9 Correct 283 ms 60788 KB Output is correct
10 Correct 91 ms 39256 KB Output is correct
11 Correct 116 ms 44948 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 43 ms 27732 KB Output is correct
17 Correct 47 ms 27740 KB Output is correct
18 Correct 141 ms 41052 KB Output is correct
19 Correct 166 ms 47292 KB Output is correct
20 Correct 122 ms 38656 KB Output is correct
21 Correct 151 ms 42816 KB Output is correct
22 Correct 121 ms 38532 KB Output is correct
23 Correct 136 ms 42664 KB Output is correct
24 Correct 43 ms 27804 KB Output is correct
25 Correct 45 ms 27740 KB Output is correct
26 Incorrect 60 ms 30800 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '16359027219341'
27 Halted 0 ms 0 KB -