oj.uz

Submission #1056946

# Submission time Handle Problem Language Result Execution time Memory
1056946 2024-08-13T12:36:59 Z noyancanturk Catfish Farm (IOI22_fish) C++17
0 / 100
 1000 ms 40384 KB 
#include "fish.h"

#include<bits/stdc++.h>
using namespace std;

using lint=long long;

const int lim=3e3+100;

using pii=pair<int,lint>;

int n,m;
lint dp[lim][lim],up[lim][lim];
vector<pii>pref[lim];
lint p(int i,int l,int r){
  auto rp=upper_bound(pref[i].begin(),pref[i].end(),pii{r,0}),
       lp=lower_bound(pref[i].begin(),pref[i].end(),pii{l,0});
  rp--;
  if(lp==pref[i].begin())return rp->second;
  lp--;
  return rp->second-lp->second;
}

lint max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
  n=N,m=M;
  for(int i=0;i<m;i++){
    pref[X[i]].push_back({Y[i]+1,W[i]});
  }
  for(int i=0;i<=n;i++){
    pref[i].push_back({0,0});
    sort(pref[i].begin(),pref[i].end());
    for(int j=1;j<pref[i].size();j++){
      pref[i][j].second+=pref[i][j-1].second;
    }
  }
  n=N,m=M;
  for(int i=0;i<=n;i++){
    dp[0][i]=p(1,0,i);
  }
  for(int i=1;i<n;i++){
    lint max1=0;
    for(int j=0;j<=n;j++){
      max1=max(max1,up[i-1][j]-p(i-1,0,j));
      dp[i][j]=max(dp[i][j],max1+p(i-1,0,j)+p(i+1,0,j));
      up[i][j]=max(up[i][j],max1+p(i-1,0,j));
      up[i][j]=max(up[i][j],dp[i-1][j]);
    }  
    max1=0;
    for(int j=n;0<=j;j--){
      max1=max(max1,dp[i-1][j]);
      dp[i][j]=max(dp[i][j],max1-p(i,0,j)+p(i+1,0,j));
    }
  }
  lint ans=0;
  for(int i=0;i<=n;i++){
    ans=max(ans,dp[n-1][i]);
  }
  return ans;
}

Compilation message

fish.cpp: In function 'lint max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:33: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]
   33 |     for(int j=1;j<pref[i].size();j++){
      |                 ~^~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1051 ms 36980 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Execution timed out 1098 ms 40384 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1027 ms 31548 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Incorrect 0 ms 2396 KB 1st lines differ - on the 1st token, expected: '4044', found: '2022'
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Incorrect 0 ms 2396 KB 1st lines differ - on the 1st token, expected: '4044', found: '2022'
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Incorrect 0 ms 2396 KB 1st lines differ - on the 1st token, expected: '4044', found: '2022'
4 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1027 ms 31548 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1051 ms 36980 KB Time limit exceeded
2 Halted 0 ms 0 KB -