oj.uz

Submission #645827

# Submission time Handle Problem Language Result Execution time Memory
645827 2022-09-28T06:30:31 Z ymm Catfish Farm (IOI22_fish) C++17
0 / 100
 74 ms 67956 KB 
#include "fish.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 1'000'010;
ll dpu[N], dpd[N];
int n, m;
vector<pii> C[N];

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
	n = N; m = M;
	Loop (i,0,m)
		C[X[i]].push_back({Y[i], i});
	Loop (i,0,n) {
		C[i].push_back({-1, m});
		X.push_back(i);
		Y.push_back(-1);
		++m;
		C[i].push_back({n, m});
		X.push_back(i);
		Y.push_back(n);
		++m;
		sort(C[i].begin(), C[i].end());
	}
	W.resize(N, 0);
	X.resize(N, 0);
	Y.resize(N, 0);

	// base
	Loop (i,0,C[0].size())
		dpu[C[0][i].second] = 0;
	dpd[C[0].front().second] = 0;
	Loop (i,1,C[0].size()) {
		int x = C[0][i].second;
		int y = C[0][i-1].second;
		dpd[x] = dpd[y] + W[x];
	}

	// second base
	dpu[C[1].back().second] = 0;
	int p = C[1].size()-1;
	LoopR (i,0,C[1].size()-1) {
		int x = C[1][i].second;
		int y = C[1][i+1].second;
		while (p > 0 && C[0][p-1].first > C[1][i].first)
			--p;
		dpu[x] = max(dpu[y], dpu[C[0][p].second]) + W[x];
	}
	dpd[C[1].front().second] = dpu[C[0].front().second];
	p = 0;
	Loop (i,1,C[1].size()) {
		int x = C[1][i].second;
		int y = C[1][i-1].second;
		while (p+1 < C[0].size() && C[0][p+1].first < C[1][i].first)
			++p;
		dpd[x] = max(dpd[y], dpd[C[0][p].second]) + W[x];
	}

	// update
	Loop (c,2,n) {
		dpu[C[c].back().second] = dpd[C[c-2].back().second];
		p = C[c].size()-1;
		LoopR (i,0,C[c].size()-1) {
			int x = C[c][i].second;
			int y = C[c][i+1].second;
			while (p > 0 && C[c-1][p-1].first > C[c][i].first)
				--p;
			dpu[x] = max(dpu[y], dpu[C[c-1][p].second]) + W[x];
		}
		dpd[C[c].front().second] = dpu[C[c-1].front().second];
		p = 0;
		Loop (i,1,C[c].size()) {
			int x = C[c][i].second;
			int y = C[c][i-1].second;
			while (p+1 < C[c-1].size() && C[c-1][p+1].first < C[c][i].first)
				++p;
			dpd[x] = max(dpd[y], dpd[C[c-1][p].second]) + W[x];
		}
	}

	// debug
	//Loop (i,0,m) {
	//	cout << "[" << X[i] << ' ' << Y[i] << ' ' << W[i] << "]: " << dpu[i] << ' ' << dpd[i] << '\n';
	//}

	// ans
	ll ans = max(dpu[C[n-1].front().second], dpd[C[n-2].back().second]);
	return ans;
}

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
fish.cpp:36:2: note: in expansion of macro 'Loop'
   36 |  Loop (i,0,C[0].size())
      |  ^~~~
fish.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
fish.cpp:39:2: note: in expansion of macro 'Loop'
   39 |  Loop (i,1,C[0].size()) {
      |  ^~~~
fish.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
fish.cpp:57:2: note: in expansion of macro 'Loop'
   57 |  Loop (i,1,C[1].size()) {
      |  ^~~~
fish.cpp:60:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   while (p+1 < C[0].size() && C[0][p+1].first < C[1][i].first)
      |          ~~~~^~~~~~~~~~~~~
fish.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
fish.cpp:78:3: note: in expansion of macro 'Loop'
   78 |   Loop (i,1,C[c].size()) {
      |   ^~~~
fish.cpp:81:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |    while (p+1 < C[c-1].size() && C[c-1][p+1].first < C[c][i].first)
      |           ~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 74 ms 67956 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 23764 KB 1st lines differ - on the 1st token, expected: '2', found: '50'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 44 ms 62568 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 23796 KB 1st lines differ - on the 1st token, expected: '3', found: '44'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 23796 KB 1st lines differ - on the 1st token, expected: '3', found: '44'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 23796 KB 1st lines differ - on the 1st token, expected: '3', found: '44'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 44 ms 62568 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 74 ms 67956 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -