oj.uz

Submission #651032

# Submission time Handle Problem Language Result Execution time Memory
651032 2022-10-16T14:10:07 Z NaimSS Catfish Farm (IOI22_fish) C++17
9 / 100
 376 ms 119796 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define Unique(v) sort(all(v));v.erase(unique(all(v)),v.end());
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define ff first
#define ss second
#define pb push_back
const int N = 100100;
typedef long long ll;
typedef pair<ll,ll> pll;
vector<pll> dp[N][2];
vector<pll> suf[N];
vector<pll> pref[N];

vector<int> posi[N];
vector<int> ys[N];
vector<pll> peixes[N];
vector<pll> peixesSum[N];
const ll inf = 1e18;
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,std::vector<int> W) {
  for(auto &it : Y)it++;
  rep(i,0,M){
    peixes[X[i]].pb(pll(Y[i],W[i]));
    ys[X[i]].pb(Y[i]);
  }

  for(int i=0;i<N;i++){
    sort(all(peixes[i]));
    rep(j,0,sz(peixes[i])){
      peixesSum[i].pb(peixes[i][j]);
      if(j)peixesSum[i][j].ss+=peixesSum[i][j-1].ss;
    }
    posi[i].pb(0);
    if(i)for(auto it : ys[i-1]){
      posi[i].pb(it);
    }
    if(i+1<N)for(auto it : ys[i+1]){
      posi[i].pb(it);
    }
    Unique(posi[i]);
  }



  for(int i=0;i<N;i++){
    
    // calc my dp

    for(int j=0;j<2;j++){

      if(j == 0){
        // subindo!
        // h(i-1) <= h(i).
        // pego um prefixo + valores dos peixes dele
        ll val=0;
        int pt=0;
        int ptPref=0;
        for(auto it : posi[i]){
          if(i == 0){
            dp[i][j].pb(pll(it,0));
            continue;
          }
          while(pt < sz(peixes[i-1]) && peixes[i-1][pt].ff<=it){
            val+=peixes[i-1][pt].ss;
            pt++;
          }
          while(ptPref + 1 < sz(pref[i-1]) && pref[i-1][ptPref+1].ff <= it)
            ptPref++;
          dp[i][j].pb(pll(it,pref[i-1][ptPref].ss + val));

        }

      }else{
        // descendo
        // h(i-1) >= h[i]
        // pega sufixo - valores dos meus peixes
        ll val=0;
        int pt=0;
        for(auto it : posi[i]){
          if(i == 0){
            dp[i][j].pb(pll(it,0));
            continue;
          }
          while(pt < sz(peixes[i]) && peixes[i][pt].ff<=it){
            val-=peixes[i][pt].ss;
            pt++;
          }
          auto ItSuf = lower_bound(all(suf[i-1]),pll(it,-inf));
          if(ItSuf == suf[i-1].end()){
            dp[i][j].pb(pll(it,0));
          }else{
            dp[i][j].pb(pll(it,val + ItSuf->ss));
          }
        }
      }

    }
    // calc pref -> subtrair os peixes de i

    ll val=0;
    int pt=0;
    for(auto it : dp[i][0]){
      while(pt < sz(peixes[i]) && peixes[i][pt].ff <= it.ff){
        val+=peixes[i][pt].ss;
        pt++;
      }
      pref[i].pb(pll(it.ff,it.ss - val));
      if(it.ff == 0){
        ll sum = (sz(peixes[i]) ? peixesSum[i].back().ss : 0);
        pref[i].back().ss = max(it.ss,dp[i][1][0].ss - sum);
      }
    }

    for(int j=1;j<sz(pref[i]);j++){
      pref[i][j].ss = max(pref[i][j].ss,pref[i][j-1].ss);
    }

    // calc suf -> somar peixes de i+1
    int K = 0;
    for(auto it : dp[i][1]){
      ll peixesNext = 0;
      if(i+1<N){
        int pos = upper_bound(all(peixes[i+1]),pll(it.ff,inf)) - peixes[i+1].begin() - 1;
        if(pos >= 0)peixesNext = peixesSum[i+1][pos].ss;
      }
      suf[i].pb(pll(it.ff,max(it.ss,dp[i][0][K].ss) + peixesNext));
      K++;
    }

    for(int j=sz(suf[i])-2;j>=0;j--){
      suf[i][j].ss = max(suf[i][j].ss,suf[i][j+1].ss);
    }
    
    continue;
    cout << "=========\n";
    rep(j,0,2){
      cout << i<<" "<<j<<endl;
      for(auto it : dp[i][j])cout << it.ff<<" "<<it.ss<<endl;


    }
      // pref:
      cout << "Pref\n";
      for(auto it : pref[i]){
        cout << it.ff<<" "<<it.ss<<endl;
      }
      cout << "Suf\n";
      for(auto it : suf[i]){
        cout << it.ff<<" "<<it.ss<<endl;
      }

    cout << "\n";

  }
  
  ll res=0;
  rep(j,0,2)for(auto it : dp[N-1][j])res=max(res,it.ss);
  return res;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 43476 KB Output is correct
2 Correct 98 ms 47316 KB Output is correct
3 Correct 38 ms 34628 KB Output is correct
4 Correct 41 ms 34740 KB Output is correct
5 Correct 303 ms 94320 KB Output is correct
6 Correct 376 ms 119796 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 155 ms 59620 KB Output is correct
3 Correct 180 ms 66904 KB Output is correct
4 Correct 86 ms 43460 KB Output is correct
5 Correct 93 ms 47424 KB Output is correct
6 Correct 13 ms 19028 KB Output is correct
7 Correct 11 ms 19024 KB Output is correct
8 Correct 11 ms 19028 KB Output is correct
9 Correct 10 ms 19028 KB Output is correct
10 Correct 40 ms 34632 KB Output is correct
11 Correct 38 ms 34732 KB Output is correct
12 Correct 106 ms 48956 KB Output is correct
13 Correct 134 ms 54108 KB Output is correct
14 Correct 112 ms 46316 KB Output is correct
15 Correct 101 ms 49384 KB Output is correct
16 Correct 92 ms 46352 KB Output is correct
17 Correct 98 ms 49276 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 34644 KB Output is correct
2 Correct 38 ms 34632 KB Output is correct
3 Incorrect 87 ms 43112 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 11 ms 19056 KB Output is correct
2 Correct 10 ms 19052 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Correct 10 ms 19112 KB Output is correct
5 Correct 13 ms 19044 KB Output is correct
6 Correct 11 ms 19108 KB Output is correct
7 Correct 13 ms 19064 KB Output is correct
8 Correct 10 ms 19028 KB Output is correct
9 Incorrect 10 ms 19156 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '165331649672'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19056 KB Output is correct
2 Correct 10 ms 19052 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Correct 10 ms 19112 KB Output is correct
5 Correct 13 ms 19044 KB Output is correct
6 Correct 11 ms 19108 KB Output is correct
7 Correct 13 ms 19064 KB Output is correct
8 Correct 10 ms 19028 KB Output is correct
9 Incorrect 10 ms 19156 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '165331649672'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19056 KB Output is correct
2 Correct 10 ms 19052 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Correct 10 ms 19112 KB Output is correct
5 Correct 13 ms 19044 KB Output is correct
6 Correct 11 ms 19108 KB Output is correct
7 Correct 13 ms 19064 KB Output is correct
8 Correct 10 ms 19028 KB Output is correct
9 Incorrect 10 ms 19156 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '165331649672'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 34644 KB Output is correct
2 Correct 38 ms 34632 KB Output is correct
3 Incorrect 87 ms 43112 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 93 ms 43476 KB Output is correct
2 Correct 98 ms 47316 KB Output is correct
3 Correct 38 ms 34628 KB Output is correct
4 Correct 41 ms 34740 KB Output is correct
5 Correct 303 ms 94320 KB Output is correct
6 Correct 376 ms 119796 KB Output is correct
7 Correct 10 ms 19028 KB Output is correct
8 Correct 155 ms 59620 KB Output is correct
9 Correct 180 ms 66904 KB Output is correct
10 Correct 86 ms 43460 KB Output is correct
11 Correct 93 ms 47424 KB Output is correct
12 Correct 13 ms 19028 KB Output is correct
13 Correct 11 ms 19024 KB Output is correct
14 Correct 11 ms 19028 KB Output is correct
15 Correct 10 ms 19028 KB Output is correct
16 Correct 40 ms 34632 KB Output is correct
17 Correct 38 ms 34732 KB Output is correct
18 Correct 106 ms 48956 KB Output is correct
19 Correct 134 ms 54108 KB Output is correct
20 Correct 112 ms 46316 KB Output is correct
21 Correct 101 ms 49384 KB Output is correct
22 Correct 92 ms 46352 KB Output is correct
23 Correct 98 ms 49276 KB Output is correct
24 Correct 51 ms 34644 KB Output is correct
25 Correct 38 ms 34632 KB Output is correct
26 Incorrect 87 ms 43112 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '16359027219341'
27 Halted 0 ms 0 KB -