oj.uz

Submission #1106874

# Submission time Handle Problem Language Result Execution time Memory
1106874 2024-10-31T08:27:33 Z pit4h Catfish Farm (IOI22_fish) C++17
9 / 100
 121 ms 30536 KB 
#include "fish.h"

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pi=pair<int,int>;
using vi=vector<int>;
#define mp make_pair
#define eb emplace_back
#define x first
#define y second
#define sz(x)int((x).size())
#define all(x)(x).begin(),(x).end()
#define rep(i,a,b)for(int i=(a);i<(b);i++)
#define per(i,a,b)for(int i=(b)-1;i>=(a);i--)
bool ckmin(auto&a,auto b){return b<a?a=b,1:0;}
bool ckmax(auto&a,auto b){return b>a?a=b,1:0;}
#ifdef LOCAL
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.x<<", "<<p.y<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto&e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X);
#else
#define debug(...){}
#endif

struct Container {
	ll shift=0,best=0;
	void add(ll delta) {
		shift += delta;
		best += delta;
	}
	void ins(ll v) {
		ckmax(best, v);
	}
	ll get() {
		return best;
	}
};

long long max_weights(int N, int M, vector<int> X, vector<int> Y,
                      vector<int> W) {

	vector<vector<pi>> sweep(N + 2);

	rep(i,0,M) {
		sweep[X[i]+1].eb(Y[i],W[i]);
	}

	rep(i,0,N+2) { 
		sweep[i].eb(N,0);
		sort(all(sweep[i]));	
	}

	vector<vector<ll>> dp(N+2);
	vector<ll> best_dp(N+2);

	rep(i,0,N+2) {
		dp[i].resize(sz(sweep[i]));
	}

	ll ans = 0;

	rep(i,1,N+1) {
		debug(i);
		int ptr_l=0,ptr_r=0;
		ll sum_l=0,sum_cur=0,sum_r=0;

		Container best_l;

		rep(j,0,sz(sweep[i])) {
			auto [y,w] = sweep[i][j];

			while (ptr_l < sz(sweep[i-1]) && sweep[i-1][ptr_l].x < y) {
				sum_l+=sweep[i-1][ptr_l].y;
				best_l.ins(dp[i-1][ptr_l]);
				best_l.add(sweep[i-1][ptr_l].y);
				ptr_l++;	
			}

			while (ptr_r < sz(sweep[i+1]) && sweep[i+1][ptr_r].x < y) {
				sum_r+=sweep[i+1][ptr_r].y;
				ptr_r++;
			}

			ckmax(dp[i][j], best_l.get());	

			ckmax(dp[i+1][ptr_r], best_l.get() + sum_r);         // cur takes from left and right
			ckmax(dp[i+1][ptr_r], best_dp[i-1] + sum_r);         // prev does not take any from column i
			ckmax(dp[i+1][ptr_r], best_dp[i] + sum_r - sum_cur); // prev takes unlimited amount from column i 

			sum_cur+=w;
		}
		
		rep(s,0,2) {
			rep(j,0,sz(sweep[i-s])) {
				ckmax(best_dp[i-s], dp[i-s][j]);
			}
			ckmax(ans, best_dp[i-s]);
		}
		debug(dp);
	}

	return ans;
}

Compilation message

fish.cpp:16:12: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   16 | bool ckmin(auto&a,auto b){return b<a?a=b,1:0;}
      |            ^~~~
fish.cpp:16:19: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   16 | bool ckmin(auto&a,auto b){return b<a?a=b,1:0;}
      |                   ^~~~
fish.cpp:17:12: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   17 | bool ckmax(auto&a,auto b){return b>a?a=b,1:0;}
      |            ^~~~
fish.cpp:17:19: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   17 | bool ckmax(auto&a,auto b){return b>a?a=b,1:0;}
      |                   ^~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 15380 KB Output is correct
2 Correct 42 ms 17704 KB Output is correct
3 Correct 13 ms 12112 KB Output is correct
4 Correct 13 ms 12112 KB Output is correct
5 Correct 121 ms 30124 KB Output is correct
6 Correct 97 ms 30536 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 60 ms 20048 KB Output is correct
3 Correct 69 ms 23356 KB Output is correct
4 Correct 34 ms 15548 KB Output is correct
5 Correct 48 ms 17732 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 504 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 14 ms 12112 KB Output is correct
11 Correct 24 ms 12112 KB Output is correct
12 Correct 34 ms 15556 KB Output is correct
13 Correct 42 ms 17836 KB Output is correct
14 Correct 41 ms 15464 KB Output is correct
15 Correct 39 ms 17084 KB Output is correct
16 Correct 35 ms 15556 KB Output is correct
17 Correct 40 ms 17084 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12112 KB Output is correct
2 Correct 14 ms 12112 KB Output is correct
3 Incorrect 27 ms 13136 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '16095792008451'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 508 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 508 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 508 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12112 KB Output is correct
2 Correct 14 ms 12112 KB Output is correct
3 Incorrect 27 ms 13136 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '16095792008451'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 15380 KB Output is correct
2 Correct 42 ms 17704 KB Output is correct
3 Correct 13 ms 12112 KB Output is correct
4 Correct 13 ms 12112 KB Output is correct
5 Correct 121 ms 30124 KB Output is correct
6 Correct 97 ms 30536 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 60 ms 20048 KB Output is correct
9 Correct 69 ms 23356 KB Output is correct
10 Correct 34 ms 15548 KB Output is correct
11 Correct 48 ms 17732 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 504 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 14 ms 12112 KB Output is correct
17 Correct 24 ms 12112 KB Output is correct
18 Correct 34 ms 15556 KB Output is correct
19 Correct 42 ms 17836 KB Output is correct
20 Correct 41 ms 15464 KB Output is correct
21 Correct 39 ms 17084 KB Output is correct
22 Correct 35 ms 15556 KB Output is correct
23 Correct 40 ms 17084 KB Output is correct
24 Correct 13 ms 12112 KB Output is correct
25 Correct 14 ms 12112 KB Output is correct
26 Incorrect 27 ms 13136 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '16095792008451'
27 Halted 0 ms 0 KB -