oj.uz

Submission #1067046

# Submission time Handle Problem Language Result Execution time Memory
1067046 2024-08-20T10:07:25 Z epicci23 Catfish Farm (IOI22_fish) C++17
9 / 100
 527 ms 71528 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++){
    
    //start
    for(int64_t j=0;j<sz(consider[i]);j++){
      dp[i][0][j]=max(dp[i][0][j],get_sum(i-1,consider[i][j]));
      dp[i][1][j]=max(dp[i][1][j],get_sum(i-1,consider[i][j])+get_sum(i+1,consider[i][j]));
    }

    // 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 0;
    };
    
    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 0;
      };

      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 0;
      };

      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;
    for(int64_t j=sz(consider[i-1])-1;j>=0;j--){
      int64_t u=consider[i-1][j];
      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));
    }
   
    for(int64_t j=0;j<sz(consider[i]);j++){
      ans=max(ans,dp[i][0][j]+get_sum(i+1,consider[i][j]));
      ans=max(ans,dp[i][1][j]);
    }
  }
  return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 37720 KB Output is correct
2 Correct 122 ms 43048 KB Output is correct
3 Correct 44 ms 27732 KB Output is correct
4 Correct 45 ms 27800 KB Output is correct
5 Correct 527 ms 71528 KB Output is correct
6 Correct 373 ms 69972 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 270 ms 49260 KB Output is correct
3 Correct 316 ms 57132 KB Output is correct
4 Correct 107 ms 37844 KB Output is correct
5 Correct 120 ms 43060 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 48 ms 27800 KB Output is correct
11 Correct 49 ms 27732 KB Output is correct
12 Correct 153 ms 39772 KB Output is correct
13 Correct 185 ms 45496 KB Output is correct
14 Correct 140 ms 37228 KB Output is correct
15 Correct 168 ms 41080 KB Output is correct
16 Correct 135 ms 37164 KB Output is correct
17 Correct 150 ms 41144 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 27728 KB Output is correct
2 Correct 46 ms 27804 KB Output is correct
3 Incorrect 60 ms 30044 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 0 ms 344 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 348 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 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 0 ms 344 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 348 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 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 0 ms 344 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 348 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 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 45 ms 27728 KB Output is correct
2 Correct 46 ms 27804 KB Output is correct
3 Incorrect 60 ms 30044 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 105 ms 37720 KB Output is correct
2 Correct 122 ms 43048 KB Output is correct
3 Correct 44 ms 27732 KB Output is correct
4 Correct 45 ms 27800 KB Output is correct
5 Correct 527 ms 71528 KB Output is correct
6 Correct 373 ms 69972 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 270 ms 49260 KB Output is correct
9 Correct 316 ms 57132 KB Output is correct
10 Correct 107 ms 37844 KB Output is correct
11 Correct 120 ms 43060 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 48 ms 27800 KB Output is correct
17 Correct 49 ms 27732 KB Output is correct
18 Correct 153 ms 39772 KB Output is correct
19 Correct 185 ms 45496 KB Output is correct
20 Correct 140 ms 37228 KB Output is correct
21 Correct 168 ms 41080 KB Output is correct
22 Correct 135 ms 37164 KB Output is correct
23 Correct 150 ms 41144 KB Output is correct
24 Correct 45 ms 27728 KB Output is correct
25 Correct 46 ms 27804 KB Output is correct
26 Incorrect 60 ms 30044 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '16359027219341'
27 Halted 0 ms 0 KB -