Submission #1040213

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1040213	2024-07-31 18:33:14	vnm06	Catfish Farm (IOI22_fish)	C++17	100 / 100	298 ms	65872 KiB

fish

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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 bests_osak[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];
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:44: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]
   44 |     for(int j=0; j<pos[i].size(); j++)
      |                  ~^~~~~~~~~~~~~~
fish.cpp:52: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]
   52 |     if(i) for(int j=0; j<pos[i-1].size(); j++) height[i].push_back(pos[i-1][j].first);
      |                        ~^~~~~~~~~~~~~~~~
fish.cpp:53: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]
   53 |     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:73:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         while(id_l+1<height[i-1].size() && height[i-1][id_l+1]<=k)
      |               ~~~~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:87:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |       if(i && id_l+1<best_dp[i-1].size()) ans2=best_dp[i-1][id_l+1]-get_sum(i, k)+get_sum(i+1, k);
      |               ~~~~~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:97:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for(int t=0; t<height[i].size(); t++)
      |                  ~^~~~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 9 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 17 / 17
• Subtask 7: 14 / 14
• Subtask 8: 16 / 16