oj.uz

답안 #651030

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
651030 2022-10-16T14:04:07 Z NaimSS 메기 농장 (IOI22_fish) C++17
6 / 100
 285 ms 94348 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 && sz(peixes[i])){
        pref[i].back().ss = max(it.ss,dp[i][1][0].ss - peixesSum[i].back().ss);
      }
    }

    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
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 43476 KB Output is correct
2 Correct 96 ms 47344 KB Output is correct
3 Correct 39 ms 34684 KB Output is correct
4 Correct 41 ms 34644 KB Output is correct
5 Incorrect 285 ms 94348 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '74762454961563'
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 19028 KB Output is correct
2 Correct 156 ms 59592 KB Output is correct
3 Correct 185 ms 66840 KB Output is correct
4 Correct 87 ms 43468 KB Output is correct
5 Correct 93 ms 47404 KB Output is correct
6 Correct 10 ms 19048 KB Output is correct
7 Correct 11 ms 19092 KB Output is correct
8 Correct 10 ms 19100 KB Output is correct
9 Correct 10 ms 19028 KB Output is correct
10 Correct 39 ms 34620 KB Output is correct
11 Correct 47 ms 34720 KB Output is correct
12 Correct 105 ms 48976 KB Output is correct
13 Correct 116 ms 54056 KB Output is correct
14 Correct 95 ms 46428 KB Output is correct
15 Correct 104 ms 49348 KB Output is correct
16 Correct 95 ms 46460 KB Output is correct
17 Correct 96 ms 49308 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 34636 KB Output is correct
2 Correct 43 ms 34636 KB Output is correct
3 Incorrect 89 ms 43128 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '16264431555488'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 18992 KB Output is correct
2 Correct 10 ms 19028 KB Output is correct
3 Correct 10 ms 19020 KB Output is correct
4 Correct 11 ms 19108 KB Output is correct
5 Correct 11 ms 19028 KB Output is correct
6 Correct 13 ms 19028 KB Output is correct
7 Correct 14 ms 19108 KB Output is correct
8 Correct 13 ms 19064 KB Output is correct
9 Incorrect 12 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

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 18992 KB Output is correct
2 Correct 10 ms 19028 KB Output is correct
3 Correct 10 ms 19020 KB Output is correct
4 Correct 11 ms 19108 KB Output is correct
5 Correct 11 ms 19028 KB Output is correct
6 Correct 13 ms 19028 KB Output is correct
7 Correct 14 ms 19108 KB Output is correct
8 Correct 13 ms 19064 KB Output is correct
9 Incorrect 12 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

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 18992 KB Output is correct
2 Correct 10 ms 19028 KB Output is correct
3 Correct 10 ms 19020 KB Output is correct
4 Correct 11 ms 19108 KB Output is correct
5 Correct 11 ms 19028 KB Output is correct
6 Correct 13 ms 19028 KB Output is correct
7 Correct 14 ms 19108 KB Output is correct
8 Correct 13 ms 19064 KB Output is correct
9 Incorrect 12 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

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 34636 KB Output is correct
2 Correct 43 ms 34636 KB Output is correct
3 Incorrect 89 ms 43128 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '16264431555488'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 43476 KB Output is correct
2 Correct 96 ms 47344 KB Output is correct
3 Correct 39 ms 34684 KB Output is correct
4 Correct 41 ms 34644 KB Output is correct
5 Incorrect 285 ms 94348 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '74762454961563'
6 Halted 0 ms 0 KB -