oj.uz

Submission #1040201

# Submission time Handle Problem Language Result Execution time Memory
1040201 2024-07-31T18:21:25 Z vnm06 Catfish Farm (IOI22_fish) C++17
0 / 100
 92 ms 40912 KB 
#include<bits/stdc++.h>
#include "fish.h"
#include <vector>

using namespace std;

int n, m;
vector<long long> sums[100005], height[100005];
vector<long long> dp[100005], dp2[100005], best_dp[100005];
vector<pair<int, int> > pos[100005];
long long bests[100005];

long long get_sum(int row, int k)
{
  if(row<0 || row>=n) return 0;
  if(sums[row].size()==0) return 0;
  int t=sums[row].size();
  if(pos[row][0].first>k) return 0;
  if(pos[row][t-1].first<=k) return sums[row][t-1];
  int le=0, ri=t;
  while(ri-le>1)
  {
    int mid=((le+ri)>>1);
    if(pos[row][mid-1].first<=k) le=mid;
    else ri=mid;
  }
  return sums[row][le-1];
}

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) 
{
  long long otg=0;
  n=N;
  m=M;
  for(int i=0; i<M; i++)
  {
    pos[X[i]].push_back({Y[i], W[i]});
  }
  for(int i=0; i<N; i++) 
  {
    sort(pos[i].begin(), pos[i].end());
    long long s=0;
    for(int j=0; j<pos[i].size(); j++)
    {
      s+=pos[i][j].second;
      sums[i].push_back(s);
    }
  }
  for(int i=0; i<N; i++)
  {
    if(i) for(int j=0; j<pos[i-1].size(); j++) height[i].push_back(pos[i-1][j].first);
    if(i<N-1) for(int j=0; j<pos[i+1].size(); j++) height[i].push_back(pos[i+1][j].first);
    sort(height[i].begin(), height[i].end());
    int id_l=-1;
    long long stv=0;

    if(i) bests[i]=bests[i-1];
    dp[i].resize(height[i].size());
    dp2[i].resize(height[i].size());
    for(int t=0; t<height[i].size(); t++)
    {
      long long ans=0, k=height[i][t], ans2=0;
      if(t && k==height[i][t-1]) continue;
      //ako ne se snizhava (mozhe i da e pyrvo)
      if(i>=3) ans=max(ans, bests[i-3]+get_sum(i-1, k)+get_sum(i+1, k));
      if(i)
      {
        while(id_l+1<height[i-1].size() && height[i-1][id_l+1]<=k) 
        {
          id_l++;
          stv=max(stv, dp[i-1][id_l]-get_sum(i, height[i-1][id_l])-get_sum(i-1, height[i-1][id_l]));
          //cout<<id_l<<endl;
        }
      }
      ans=max(ans, stv+get_sum(i-1, k)+get_sum(i+1, k));
      dp[i][t]=ans;
      otg=max(otg, ans);
      bests[i]=max(bests[i], dp[i][t]);

      if(i) ans2=best_dp[i-1][id_l+1]-get_sum(i, k)+get_sum(i+1, k);
      dp2[i][t]=ans2;
      otg=max(otg, ans2);
      bests[i]=max(bests[i], dp2[i][t]);
    
      //cout<<i<<" "<<height[i][t]<<" "<<dp[i][t]<<" "<<dp2[i][t]<<endl;
      //ako trygne da se snizhava
    
    }
    for(int t=0; t<height[i].size(); t++)
    {
      best_dp[i].push_back(max(dp[i][t], dp2[i][t]));
    }
    for(int t=height[i].size()-2; t>=0; t--) best_dp[i][t]=max(best_dp[i][t], best_dp[i][t+1]);
  }
  return otg;
}

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int j=0; j<pos[i].size(); j++)
      |                  ~^~~~~~~~~~~~~~
fish.cpp:51:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     if(i) for(int j=0; j<pos[i-1].size(); j++) height[i].push_back(pos[i-1][j].first);
      |                        ~^~~~~~~~~~~~~~~~
fish.cpp:52:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     if(i<N-1) for(int j=0; j<pos[i+1].size(); j++) height[i].push_back(pos[i+1][j].first);
      |                            ~^~~~~~~~~~~~~~~~
fish.cpp:60:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int t=0; t<height[i].size(); t++)
      |                  ~^~~~~~~~~~~~~~~~~
fish.cpp:68:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         while(id_l+1<height[i-1].size() && height[i-1][id_l+1]<=k)
      |               ~~~~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:89:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int t=0; t<height[i].size(); t++)
      |                  ~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 40912 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14428 KB Output is correct
2 Correct 83 ms 32132 KB Output is correct
3 Correct 92 ms 36028 KB Output is correct
4 Runtime error 36 ms 40912 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 29016 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14432 KB Output is correct
2 Correct 5 ms 14428 KB Output is correct
3 Correct 5 ms 14428 KB Output is correct
4 Correct 5 ms 14428 KB Output is correct
5 Correct 5 ms 14304 KB Output is correct
6 Correct 5 ms 14428 KB Output is correct
7 Correct 5 ms 14424 KB Output is correct
8 Correct 6 ms 14428 KB Output is correct
9 Incorrect 6 ms 14376 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '214837477243'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14432 KB Output is correct
2 Correct 5 ms 14428 KB Output is correct
3 Correct 5 ms 14428 KB Output is correct
4 Correct 5 ms 14428 KB Output is correct
5 Correct 5 ms 14304 KB Output is correct
6 Correct 5 ms 14428 KB Output is correct
7 Correct 5 ms 14424 KB Output is correct
8 Correct 6 ms 14428 KB Output is correct
9 Incorrect 6 ms 14376 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '214837477243'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14432 KB Output is correct
2 Correct 5 ms 14428 KB Output is correct
3 Correct 5 ms 14428 KB Output is correct
4 Correct 5 ms 14428 KB Output is correct
5 Correct 5 ms 14304 KB Output is correct
6 Correct 5 ms 14428 KB Output is correct
7 Correct 5 ms 14424 KB Output is correct
8 Correct 6 ms 14428 KB Output is correct
9 Incorrect 6 ms 14376 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '214837477243'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 29016 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 40912 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -