oj.uz

답안 #651027

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
651027 2022-10-16T13:41:16 Z NaimSS 메기 농장 (IOI22_fish) C++17
6 / 100
 279 ms 100476 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));
    }

    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 81 ms 43584 KB Output is correct
2 Correct 95 ms 48956 KB Output is correct
3 Correct 38 ms 34744 KB Output is correct
4 Correct 38 ms 34708 KB Output is correct
5 Incorrect 279 ms 100476 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '44945481875572'
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 162 ms 59604 KB Output is correct
3 Correct 182 ms 69988 KB Output is correct
4 Correct 91 ms 44620 KB Output is correct
5 Correct 100 ms 48868 KB Output is correct
6 Correct 12 ms 19028 KB Output is correct
7 Correct 10 ms 19088 KB Output is correct
8 Correct 10 ms 19028 KB Output is correct
9 Correct 10 ms 19032 KB Output is correct
10 Correct 37 ms 34740 KB Output is correct
11 Correct 40 ms 34696 KB Output is correct
12 Correct 99 ms 50080 KB Output is correct
13 Correct 123 ms 55548 KB Output is correct
14 Correct 91 ms 47512 KB Output is correct
15 Correct 103 ms 50836 KB Output is correct
16 Correct 92 ms 47580 KB Output is correct
17 Correct 107 ms 50764 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 34648 KB Output is correct
2 Correct 37 ms 34748 KB Output is correct
3 Incorrect 90 ms 43724 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '1999703533'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 19072 KB Output is correct
2 Correct 10 ms 19028 KB Output is correct
3 Correct 12 ms 19028 KB Output is correct
4 Correct 11 ms 19028 KB Output is correct
5 Correct 10 ms 19028 KB Output is correct
6 Correct 11 ms 19028 KB Output is correct
7 Correct 11 ms 19008 KB Output is correct
8 Correct 10 ms 19088 KB Output is correct
9 Incorrect 11 ms 19156 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '7818664569'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 19072 KB Output is correct
2 Correct 10 ms 19028 KB Output is correct
3 Correct 12 ms 19028 KB Output is correct
4 Correct 11 ms 19028 KB Output is correct
5 Correct 10 ms 19028 KB Output is correct
6 Correct 11 ms 19028 KB Output is correct
7 Correct 11 ms 19008 KB Output is correct
8 Correct 10 ms 19088 KB Output is correct
9 Incorrect 11 ms 19156 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '7818664569'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 19072 KB Output is correct
2 Correct 10 ms 19028 KB Output is correct
3 Correct 12 ms 19028 KB Output is correct
4 Correct 11 ms 19028 KB Output is correct
5 Correct 10 ms 19028 KB Output is correct
6 Correct 11 ms 19028 KB Output is correct
7 Correct 11 ms 19008 KB Output is correct
8 Correct 10 ms 19088 KB Output is correct
9 Incorrect 11 ms 19156 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '7818664569'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 34648 KB Output is correct
2 Correct 37 ms 34748 KB Output is correct
3 Incorrect 90 ms 43724 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '1999703533'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 43584 KB Output is correct
2 Correct 95 ms 48956 KB Output is correct
3 Correct 38 ms 34744 KB Output is correct
4 Correct 38 ms 34708 KB Output is correct
5 Incorrect 279 ms 100476 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '44945481875572'
6 Halted 0 ms 0 KB -