oj.uz

Submission #626272

# Submission time Handle Problem Language Result Execution time Memory
626272 2022-08-11T10:45:07 Z Antekb Catfish Farm (IOI22_fish) C++17
0 / 100
 172 ms 32404 KB 
#include "fish.h"
#include <bits/stdc++.h>
#define pb push_back
#define st first
#define nd second
using namespace std;
using ll = long long;
const int INF=1e9+5;
ll max_weights(int n, int m, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
	for(auto &i:X)i++;
	vector<pair<int, int> > V[n+2];	
	vector<ll> dp[n+2][2];
	ll dp2[n+2][2];
	for(int i=0; i<=n+1; i++)dp2[i][0]=dp2[i][1]=0;
	for(int i=0; i<m; i++){
		V[X[i]].pb({Y[i], W[i]});
	}
	for(int i=0; i<=n+1; i++){
		V[i].pb({n, INF});
		sort(V[i].begin(), V[i].end());
		dp[i][0].resize(V[i].size());
		dp[i][1].resize(V[i].size());
	}
	dp[0][0][1]=dp[0][0][0]=-1e18;
	for(int i=1; i<=n+1; i++){
		ll s=0;
		int wsk=0;
		for(int j=0; j<V[i-1].size(); j++){
			dp[i-1][j][0]-=s;
			s+=V[i-1][j].nd;
		}
		ll m=dp2[i-1][0];
		dp2[i][0]=max(dp2[i-1][0], dp2[i-1][1]);
		s=0;
		for(int j=0; j<V[i].size(); j++){
			while(wsk<V[i-1].size() && V[i][j].st>V[i-1][wsk].st){
				m=max(m, dp[i-1][wsk][0]);
				s+=V[i-1][wsk].nd;
				wsk++;
			}
			dp[i][j][0]=s+m;
		}
		wsk=V[i-1].size()-1;
		m=dp[i-1][wsk][1];
		for(int j=V[i].size()-2; j>=0; j--){
			while(wsk!=0 && V[i-1][wsk-1].st>V[i][j].st){
				m=max(m, dp[i-1][wsk-1][1]);
				wsk--;
			}
			dp[i][j][1]=m;
			m+=V[i][j].nd;
		}
		for(int j=0; j<V[i-1].size(); j++)dp2[i][0]=max(dp2[i][0], dp[i-1][j][1]);
		dp2[i][1]=max(m, dp2[i][0]);
		for(int j=0; j<V[i].size(); j++){
			dp[i][j][0]=max(dp[i][j][0], dp2[i-1][1]);
		}
		for(int j=0; j<V[i].size(); j++){
			dp[i][j][1]=max(dp[i][j][0], dp[i][j][1]);
		}
		//cout<<i<<"\n";
		//cout<<dp2[i][0]<<" "<<dp2[i][1]<<" a\n";
		for(int j=0; j<=V[i].size(); j++){
			//cout<<dp[i][j][0]<<" "<<dp[i][j][1]<<" b\n";
		}
	}
	return dp2[n+1][0];
}

Compilation message

fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:28:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   for(int j=0; j<V[i-1].size(); j++){
      |                ~^~~~~~~~~~~~~~
fish.cpp:35:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for(int j=0; j<V[i].size(); j++){
      |                ~^~~~~~~~~~~~
fish.cpp:36:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |    while(wsk<V[i-1].size() && V[i][j].st>V[i-1][wsk].st){
      |          ~~~^~~~~~~~~~~~~~
fish.cpp:53:17: 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 |   for(int j=0; j<V[i-1].size(); j++)dp2[i][0]=max(dp2[i][0], dp[i-1][j][1]);
      |                ~^~~~~~~~~~~~~~
fish.cpp:55:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for(int j=0; j<V[i].size(); j++){
      |                ~^~~~~~~~~~~~
fish.cpp:58:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for(int j=0; j<V[i].size(); j++){
      |                ~^~~~~~~~~~~~
fish.cpp:63:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(int j=0; j<=V[i].size(); j++){
      |                ~^~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 20288 KB Output is correct
2 Correct 63 ms 22976 KB Output is correct
3 Correct 26 ms 18224 KB Output is correct
4 Correct 35 ms 18260 KB Output is correct
5 Incorrect 172 ms 32404 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '149814466843847'
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 105 ms 24108 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '8043712411108008'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 18260 KB Output is correct
2 Correct 33 ms 18256 KB Output is correct
3 Incorrect 49 ms 17712 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '21049836049923'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 1 ms 212 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 1 ms 212 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 1 ms 212 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 25 ms 18260 KB Output is correct
2 Correct 33 ms 18256 KB Output is correct
3 Incorrect 49 ms 17712 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '21049836049923'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 20288 KB Output is correct
2 Correct 63 ms 22976 KB Output is correct
3 Correct 26 ms 18224 KB Output is correct
4 Correct 35 ms 18260 KB Output is correct
5 Incorrect 172 ms 32404 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '149814466843847'
6 Halted 0 ms 0 KB -