| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 829321 |
2023-08-18T09:15:54 Z |
tolbi |
Catfish Farm (IOI22_fish) |
C++17 |
|
1000 ms |
40704 KB |
#include <bits/stdc++.h>
using namespace std;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
typedef long long ll;
#include "fish.h"
vector<vector<ll>> dp;
vector<int> X,Y;
int N,M;
vector<vector<pair<int,pair<ll,int>>>> arr;
ll query(int x, int l, int r){
ll rval = 0;
for (int i = 0; i < arr[x].size(); i++){
if (arr[x][i].first>=l && arr[x][i].first<=r){
rval+=arr[x][i].second.first;
}
}
return rval;
}
int getup(int node){
int xv = X[node];
int yv = Y[node];
for (int i = 0; i < arr[xv].size(); i++){
if (arr[xv][i].first>yv){
return arr[xv][i].second.second;
}
}
assert(false);
return 23;
}
int getdown(int node){
int xv = X[node];
int yv = Y[node];
for (int i = arr[xv].size()-1; i >= 0; i--){
if (arr[xv][i].first<yv){
return arr[xv][i].second.second;
}
}
assert(false);
return 23;
}
int getnextup(int node){
int xv = X[node];
int yv = Y[node];
for (int i = 0; i < arr[xv+1].size(); i++){
if (arr[xv+1][i].first>=yv){
return arr[xv+1][i].second.second;
}
}
assert(false);
return 23;
}
int getnextdown(int node){
int xv = X[node];
int yv = Y[node];
for (int i = arr[xv+1].size()-1; i >= 0; i--){
if (arr[xv+1][i].first<=yv){
return arr[xv+1][i].second.second;
}
}
assert(false);
return 23;
}
long long f(int node, int flag){
int x = X[node];
int y = Y[node];
if (dp[node][flag]!=-1) return dp[node][flag];
if (flag==1){
dp[node][flag]=0;
if (y<N){
ll crr = 0;
if (x>0) crr = query(x-1,y,y);
dp[node][flag]=crr+f(getup(node),1);
}
if (x+1<N){
int next = getnextup(node);
ll crr = query(x,y,Y[next]-1);
dp[node][flag]=max(dp[node][flag],crr+f(next,1));
next=getnextdown(node);
crr = query(x+1,Y[next],y-1);
dp[node][flag]=max(dp[node][flag],crr+f(next,0));
}
}
else if (flag==0){
dp[node][flag]=0;
if (y-1>=0){
dp[node][flag]=query(x,y-1,y-1)+f(getdown(node),0);
}
if (x+1<N){
dp[node][flag]=max(dp[node][flag],f(getnextup(node),0));
if (y==0){
dp[node][flag]=max(dp[node][flag],f(M+x+1,2));
}
}
}
else {
dp[node][flag]=0;
if (y<N){
dp[node][flag]=f(getup(node),2);
}
if (x+1<N){
int next = getnextup(node);
ll crr = query(x,y,Y[next]-1);
dp[node][flag]=max(dp[node][flag],crr+f(next,1));
next=getnextdown(node);
crr = query(x+1,Y[next],y-1);
dp[node][flag]=max(dp[node][flag],crr+f(next,0));
}
}
if (flag!=0 && x+2<N){
dp[node][flag]=max(dp[node][flag],f(M+x+2,1));
}
return dp[node][flag];
};
long long max_weights(int _N, int _M, std::vector<int> _X, std::vector<int> _Y, std::vector<int> _W) {
N=_N;
X=_X,Y=_Y;
vector<int> W=_W;
arr.resize(N);
vector<int> bb(N,0);
for (int i = 0; i < M; ++i)
{
if (_Y[i]==0) bb[_X[i]]=W[i];
else {
X.push_back(_X[i]);
Y.push_back(_Y[i]);
W.push_back(_W[i]);
}
}
for (int i = 0; i < N; ++i)
{
X.push_back(i);
Y.push_back(0);
W.push_back(bb[i]);
}
for (int i = 0; i < N; i++){
X.push_back(i);
Y.push_back(N);
W.push_back(0);
}
for (int i = 0; i < Y.size(); i++){
arr[X[i]].push_back({Y[i],{W[i],i}});
}
for (int i = 0; i < N; ++i)
{
sort(arr[i].begin(), arr[i].end());
}
//0 decreasing
//1 increasing
//2 increasing, \
but forbidden to profit from back
dp.resize(Y.size(),vector<ll>(3,-1));
return f(M,2);
}
Compilation message
fish.cpp:150:5: warning: multi-line comment [-Wcomment]
150 | //2 increasing, \
| ^
fish.cpp: In function 'll query(int, int, int)':
fish.cpp:12:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<long long int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | for (int i = 0; i < arr[x].size(); i++){
| ~~^~~~~~~~~~~~~~~
fish.cpp: In function 'int getup(int)':
fish.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<long long int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for (int i = 0; i < arr[xv].size(); i++){
| ~~^~~~~~~~~~~~~~~~
fish.cpp: In function 'int getnextup(int)':
fish.cpp:44:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<long long int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for (int i = 0; i < arr[xv+1].size(); i++){
| ~~^~~~~~~~~~~~~~~~~~
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:141:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
141 | for (int i = 0; i < Y.size(); i++){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1091 ms |
33448 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Execution timed out |
1083 ms |
40704 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
30396 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
22548 KB |
1st lines differ - on the 1st token, expected: '882019', found: '0' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '3', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '3', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '3', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
30396 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
22548 KB |
1st lines differ - on the 1st token, expected: '882019', found: '0' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1091 ms |
33448 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
