oj.uz

답안 #625764

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
625764 2022-08-10T18:44:13 Z inwbear 메기 농장 (IOI22_fish) C++17
14 / 100
 132 ms 49024 KB 
//#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define imx INT_MAX
const long long MMX = (long long)(1e18);
typedef long long LL;
vector<pair<int,LL> > dw[100005],val[100005];
vector<pair<int,pair<int,int> > >up[100005];
vector<pair<LL,int> >lup[100005],ldw[100005],lze[100005];
vector<LL>rup[100005];
int c1,c2,si1,si2,c3,cr,crr;
LL ze[100005],rr,rrdw,rrup;

long long max_weights(int N,int M,vector<int>X,vector<int>Y,vector<int>W){
  for(int i=0;i<M;i++){
    up[X[i]+2].pb({Y[i]+1,{W[i],-1}});
    up[X[i]].pb({Y[i]+1,{W[i],1}});
    dw[X[i]].pb({Y[i]+1,W[i]});
    val[X[i]+1].pb({Y[i]+1,W[i]});
  }
  for(int i=1;i<=N;i++){
      sort(all(up[i]));
      sort(all(dw[i]));
      sort(all(val[i]));
  }
  lze[0].pb({0,0});
  for(int i=1;i<=N;i++){
    for(int j=0;j<dw[i].size();j++){
      ldw[i].pb({0,dw[i][j].F});
      if(j!=0)dw[i][j].S+=dw[i][j-1].S;
    }

    c1=lup[i-1].size()-1,c2=ldw[i-1].size()-1,c3=val[i].size()-1,rr=-1;
    rrdw=0;
    for(int j=0;j<val[i].size();j++)rrdw+=val[i][j].S;
    for(int j=ldw[i].size()-1;j>-1;j--){
      cr=ldw[i][j].S;
      if(c1!=-1){
        while(lup[i-1][c1].S>=cr){
          rr=max(rr,lup[i-1][c1].F);
          c1--;
          if(c1==-1)break;
        }
      }
      if(c2!=-1){
        while(ldw[i-1][c2].S>=cr){
          rr=max(rr,ldw[i-1][c2].F);
          c2--;
          if(c2==-1)break;
        }
      }
      if(c3!=-1){
        while(val[i][c3].F>cr){
          rrdw-=val[i][c3].S;
          c3--;
          if(c3==-1)break;
        }
      }
      if(rr==-1)continue;
      ldw[i][j].F=rr+dw[i][j].S-rrdw;
    }

    c1=0,c2=0,c3=0,rrup=0,rrdw=0,rr=-MMX;
    for(int j=0;j<up[i].size();j++){
      rrup+=up[i][j].S.F;
      if(j!=up[i].size()-1){
        if(up[i][j].F==up[i][j+1].F)continue;
      }
      cr=up[i][j].F;
      if(c1!=lup[i-1].size()){
        while(lup[i-1][c1].S<=cr){
          crr=lup[i-1][c1].S;
          if(c2!=val[i-1].size()){
            while(val[i-1][c2].F<=crr){
              rrdw-=val[i-1][c2].S;
              c2++;
              if(c2==val[i-1].size())break;
            }
          }
          if(c3!=val[i].size()){
            while(val[i][c3].F<=crr){
              rrdw-=val[i][c3].S;
              c3++;
              if(c3==val[i].size())break;
            }
          }
          //printf("// %lld",rrdw);
          rr=max(rr,lup[i-1][c1].F+rrdw);
          c1++;
          if(c1==lup[i-1].size())break;
        }
      }
      rup[i].pb(rrup);
      if(rr==-MMX){
        lup[i].pb({0,up[i][j].F});
        continue;
      }
      //printf("=/ %lld %lld",rrup,rr);
      lup[i].pb({rrup+rr,up[i][j].F});
    }

    c1=lze[i-1].size()-1,c2=val[i-1].size()-1,rrdw=0,rr=-1;
    for(int j=0;j<val[i-1].size();j++)rrdw-=val[i-1][j].S;
    for(int j=lup[i].size()-1;j>-1;j--){
      cr=lup[i][j].S;
      if(c1!=-1){
        while(lze[i-1][c1].S>=cr){
          rr=max(rr,lze[i-1][c1].F);
          c1--;
          if(c1==-1)break;
        }
      }
      if(c2!=-1){
        while(val[i-1][c2].F>cr){
          rrdw+=val[i-1][c2].S;
          c2--;
          if(c2==-1)break;
        }
      }
      if(rr==-1)continue;
      //printf("//%d %lld\n",lup[i][j].S,rr+rup[i][j]+rrdw);
      lup[i][j].F=max(lup[i][j].F,rr+rup[i][j]+rrdw);
    }

    c1=0,c2=0,rr=-1,rrdw=0;
    for(int j=0;j<lup[i].size();j++){
      cr=lup[i][j].S;
      if(c1!=lze[i-1].size()){
        while(lze[i-1][c1].S<=cr){
          crr=lze[i-1][c1].S;
          if(c2!=val[i-1].size()){
            while(val[i-1][c2].F<=crr){
              rrdw-=val[i-1][c2].S;
              c2++;
              if(c2==val[i-1].size())break;
            }
          }
          rr=max(rr,lze[i-1][c1].F+rrdw);
          c1++;
          if(c1==lze[i-1].size())break;
        }
      }
      if(rr==-1)continue;
      lup[i][j].F=max(lup[i][j].F,rr+rup[i][j]);
    }
    lze[i].pb({ze[i-1],0});
    si1=lup[i-1].size();
    si2=ldw[i-1].size();
    lup[i-1].pb({0,imx});
    ldw[i-1].pb({0,imx});
    for(c1=0,c2=0;c1<si1||c2<si2;){
      ze[i]=max(ze[i],lup[i-1][c1].F);
      ze[i]=max(ze[i],ldw[i-1][c2].F);
      if(lup[i-1][c1].S<ldw[i-1][c2].S){
        lze[i].pb(lup[i-1][c1]);
        c1++;
      }
      else if(lup[i-1][c1].S>ldw[i-1][c2].S){
        lze[i].pb(ldw[i-1][c2]);
        c2++;
      }
      else{
        lze[i].pb({max(lup[i-1][c1].F,ldw[i-1][c2].F),lup[i-1][c1].S});
        c1++,c2++;
      }
    }
    //printf("=%d=\n",i);
    // for(int j=0;j<lup[i].size();j++)printf("%lld %d\n",lup[i][j].F,lup[i][j].S);
    // for(int j=0;j<ldw[i].size();j++)printf("[%lld %d]\n",ldw[i][j].F,ldw[i][j].S);
    // for(int j=0;j<lze[i].size();j++)printf("{%lld %d}\n",lze[i][j].F,lze[i][j].S);
  }
  LL ans=0;
  for(int i=0;i<lze[N].size();i++)ans=max(ans,lze[N][i].F);
  for(int i=0;i<lup[N].size();i++)ans=max(ans,lup[N][i].F);
  for(int i=0;i<ldw[N].size();i++)ans=max(ans,ldw[N][i].F);
  return ans;
}

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int j=0;j<dw[i].size();j++){
      |                 ~^~~~~~~~~~~~~
fish.cpp:39:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int j=0;j<val[i].size();j++)rrdw+=val[i][j].S;
      |                 ~^~~~~~~~~~~~~~
fish.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int j=0;j<up[i].size();j++){
      |                 ~^~~~~~~~~~~~~
fish.cpp:70:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |       if(j!=up[i].size()-1){
      |          ~^~~~~~~~~~~~~~~~
fish.cpp:74:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |       if(c1!=lup[i-1].size()){
      |          ~~^~~~~~~~~~~~~~~~~
fish.cpp:77:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |           if(c2!=val[i-1].size()){
      |              ~~^~~~~~~~~~~~~~~~~
fish.cpp:81:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |               if(c2==val[i-1].size())break;
      |                  ~~^~~~~~~~~~~~~~~~~
fish.cpp:84:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |           if(c3!=val[i].size()){
      |              ~~^~~~~~~~~~~~~~~
fish.cpp:88:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |               if(c3==val[i].size())break;
      |                  ~~^~~~~~~~~~~~~~~
fish.cpp:94:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |           if(c1==lup[i-1].size())break;
      |              ~~^~~~~~~~~~~~~~~~~
fish.cpp:107:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for(int j=0;j<val[i-1].size();j++)rrdw-=val[i-1][j].S;
      |                 ~^~~~~~~~~~~~~~~~
fish.cpp:130:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |     for(int j=0;j<lup[i].size();j++){
      |                 ~^~~~~~~~~~~~~~
fish.cpp:132:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |       if(c1!=lze[i-1].size()){
      |          ~~^~~~~~~~~~~~~~~~~
fish.cpp:135:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |           if(c2!=val[i-1].size()){
      |              ~~^~~~~~~~~~~~~~~~~
fish.cpp:139:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |               if(c2==val[i-1].size())break;
      |                  ~~^~~~~~~~~~~~~~~~~
fish.cpp:144:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |           if(c1==lze[i-1].size())break;
      |              ~~^~~~~~~~~~~~~~~~~
fish.cpp:177:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |   for(int i=0;i<lze[N].size();i++)ans=max(ans,lze[N][i].F);
      |               ~^~~~~~~~~~~~~~
fish.cpp:178:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |   for(int i=0;i<lup[N].size();i++)ans=max(ans,lup[N][i].F);
      |               ~^~~~~~~~~~~~~~
fish.cpp:179:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |   for(int i=0;i<ldw[N].size();i++)ans=max(ans,ldw[N][i].F);
      |               ~^~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 68 ms 34592 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '0'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Incorrect 132 ms 49024 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '0'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 26 ms 26068 KB 1st lines differ - on the 1st token, expected: '10082010', found: '0'
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 16724 KB Output is correct
2 Correct 9 ms 16668 KB Output is correct
3 Correct 9 ms 16664 KB Output is correct
4 Correct 10 ms 16740 KB Output is correct
5 Correct 10 ms 16724 KB Output is correct
6 Correct 10 ms 16724 KB Output is correct
7 Correct 11 ms 16724 KB Output is correct
8 Correct 9 ms 16724 KB Output is correct
9 Correct 10 ms 16872 KB Output is correct
10 Correct 11 ms 17108 KB Output is correct
11 Correct 10 ms 16832 KB Output is correct
12 Correct 10 ms 16980 KB Output is correct
13 Correct 10 ms 16788 KB Output is correct
14 Correct 9 ms 16900 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 16724 KB Output is correct
2 Correct 9 ms 16668 KB Output is correct
3 Correct 9 ms 16664 KB Output is correct
4 Correct 10 ms 16740 KB Output is correct
5 Correct 10 ms 16724 KB Output is correct
6 Correct 10 ms 16724 KB Output is correct
7 Correct 11 ms 16724 KB Output is correct
8 Correct 9 ms 16724 KB Output is correct
9 Correct 10 ms 16872 KB Output is correct
10 Correct 11 ms 17108 KB Output is correct
11 Correct 10 ms 16832 KB Output is correct
12 Correct 10 ms 16980 KB Output is correct
13 Correct 10 ms 16788 KB Output is correct
14 Correct 9 ms 16900 KB Output is correct
15 Correct 11 ms 16724 KB Output is correct
16 Incorrect 10 ms 17108 KB 1st lines differ - on the 1st token, expected: '741526820812', found: '131260577826'
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 16724 KB Output is correct
2 Correct 9 ms 16668 KB Output is correct
3 Correct 9 ms 16664 KB Output is correct
4 Correct 10 ms 16740 KB Output is correct
5 Correct 10 ms 16724 KB Output is correct
6 Correct 10 ms 16724 KB Output is correct
7 Correct 11 ms 16724 KB Output is correct
8 Correct 9 ms 16724 KB Output is correct
9 Correct 10 ms 16872 KB Output is correct
10 Correct 11 ms 17108 KB Output is correct
11 Correct 10 ms 16832 KB Output is correct
12 Correct 10 ms 16980 KB Output is correct
13 Correct 10 ms 16788 KB Output is correct
14 Correct 9 ms 16900 KB Output is correct
15 Correct 11 ms 16724 KB Output is correct
16 Incorrect 10 ms 17108 KB 1st lines differ - on the 1st token, expected: '741526820812', found: '131260577826'
17 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 26 ms 26068 KB 1st lines differ - on the 1st token, expected: '10082010', found: '0'
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 68 ms 34592 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '0'
2 Halted 0 ms 0 KB -