oj.uz

Submission #630073

# Submission time Handle Problem Language Result Execution time Memory
630073 2022-08-15T15:48:18 Z ash7728 Catfish Farm (IOI22_fish) C++17
3 / 100
 1000 ms 56860 KB 
#include "fish.h"
#include <bits/stdc++.h>
#define N 300020
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = (ll)(1e17);

int n, m;
ll pref[N];
vector<vector<int>> fish;
vector<vector<int>> col[N];

ll max_weights(int n_, int m_, vector<int> X, vector<int> Y, vector<int> W) {
	n=n_,m=m_;
	for(int i = 0; i < m; i++){
		fish.pb({X[i], Y[i], W[i]});
		col[X[i]].pb({Y[i], W[i], i});
	}
	for(int c = 0;c < n; c++){
		sort(all(col[c]));
		ll acum = 0;
		for(auto x: col[c]) acum += W[x[2]],pref[x[2]]=acum;
	}
	vector<ll> olds = {0,0}, dp(m+1);
	for(int c = 0; c < n; c++){
		ll opt = -INF;
		for(auto x: col[c]){
			dp[x[2]] = min(INF,olds[sz(olds)-2] + pref[x[2]]);		
			
			if(c >= 1 and c < n-1){
				for(auto v: col[c-1]){
					ll cost = 0, cost2=0;

					vector<int> cc = {Y[v[2]],(int)(1e9),(int)(1e9)};
					auto it = upper_bound(all(col[c]), cc);
					if(it != col[c].begin()){
						--it;
						cost = pref[(*it)[2]];
					}

					if(Y[v[2]] <= Y[x[2]]){
						dp[x[2]] = max(dp[x[2]], dp[v[2]] + pref[x[2]] -cost);
					}
				}
			}
			else if(c == 0)dp[x[2]] = pref[x[2]];

			opt=max(opt, dp[x[2]]);
		}
		olds.pb(max(olds.back(), opt));
	}

	return olds.back();
}

Compilation message

fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:36:19: warning: unused variable 'cost2' [-Wunused-variable]
   36 |      ll cost = 0, cost2=0;
      |                   ^~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 21076 KB Output is correct
2 Correct 83 ms 24008 KB Output is correct
3 Correct 5 ms 8524 KB Output is correct
4 Correct 5 ms 8396 KB Output is correct
5 Correct 344 ms 53840 KB Output is correct
6 Correct 289 ms 56860 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7252 KB Output is correct
2 Execution timed out 1078 ms 31348 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8524 KB Output is correct
2 Correct 8 ms 8524 KB Output is correct
3 Incorrect 47 ms 17356 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '16359027219341'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 6 ms 7324 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 4 ms 7252 KB Output is correct
7 Correct 5 ms 7268 KB Output is correct
8 Incorrect 4 ms 7252 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 4 ms 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 6 ms 7324 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 4 ms 7252 KB Output is correct
7 Correct 5 ms 7268 KB Output is correct
8 Incorrect 4 ms 7252 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 4 ms 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 6 ms 7324 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 4 ms 7252 KB Output is correct
7 Correct 5 ms 7268 KB Output is correct
8 Incorrect 4 ms 7252 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 7 ms 8524 KB Output is correct
2 Correct 8 ms 8524 KB Output is correct
3 Incorrect 47 ms 17356 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '16359027219341'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 21076 KB Output is correct
2 Correct 83 ms 24008 KB Output is correct
3 Correct 5 ms 8524 KB Output is correct
4 Correct 5 ms 8396 KB Output is correct
5 Correct 344 ms 53840 KB Output is correct
6 Correct 289 ms 56860 KB Output is correct
7 Correct 5 ms 7252 KB Output is correct
8 Execution timed out 1078 ms 31348 KB Time limit exceeded
9 Halted 0 ms 0 KB -