oj.uz

Submission #645829

# Submission time Handle Problem Language Result Execution time Memory
645829 2022-09-28T06:35:10 Z ymm Catfish Farm (IOI22_fish) C++17
6 / 100
 184 ms 105092 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 Correct 55 ms 44032 KB Output is correct
2 Correct 64 ms 45280 KB Output is correct
3 Correct 30 ms 41708 KB Output is correct
4 Correct 30 ms 41756 KB Output is correct
5 Runtime error 184 ms 105092 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 35540 KB Output is correct
2 Correct 87 ms 46884 KB Output is correct
3 Correct 100 ms 48792 KB Output is correct
4 Correct 57 ms 44032 KB Output is correct
5 Correct 66 ms 45276 KB Output is correct
6 Correct 18 ms 35504 KB Output is correct
7 Correct 18 ms 35540 KB Output is correct
8 Correct 17 ms 35540 KB Output is correct
9 Correct 17 ms 35460 KB Output is correct
10 Correct 31 ms 41732 KB Output is correct
11 Correct 31 ms 41720 KB Output is correct
12 Correct 61 ms 43956 KB Output is correct
13 Correct 65 ms 45336 KB Output is correct
14 Correct 57 ms 44040 KB Output is correct
15 Correct 65 ms 45060 KB Output is correct
16 Correct 59 ms 43956 KB Output is correct
17 Correct 63 ms 44880 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 41704 KB Output is correct
2 Correct 30 ms 41756 KB Output is correct
3 Incorrect 63 ms 43744 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '20897672610412'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 35464 KB Output is correct
2 Correct 22 ms 35540 KB Output is correct
3 Correct 23 ms 35540 KB Output is correct
4 Correct 17 ms 35540 KB Output is correct
5 Correct 17 ms 35536 KB Output is correct
6 Correct 17 ms 35540 KB Output is correct
7 Correct 18 ms 35480 KB Output is correct
8 Correct 17 ms 35540 KB Output is correct
9 Incorrect 17 ms 35540 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '214837477243'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 35464 KB Output is correct
2 Correct 22 ms 35540 KB Output is correct
3 Correct 23 ms 35540 KB Output is correct
4 Correct 17 ms 35540 KB Output is correct
5 Correct 17 ms 35536 KB Output is correct
6 Correct 17 ms 35540 KB Output is correct
7 Correct 18 ms 35480 KB Output is correct
8 Correct 17 ms 35540 KB Output is correct
9 Incorrect 17 ms 35540 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '214837477243'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 35464 KB Output is correct
2 Correct 22 ms 35540 KB Output is correct
3 Correct 23 ms 35540 KB Output is correct
4 Correct 17 ms 35540 KB Output is correct
5 Correct 17 ms 35536 KB Output is correct
6 Correct 17 ms 35540 KB Output is correct
7 Correct 18 ms 35480 KB Output is correct
8 Correct 17 ms 35540 KB Output is correct
9 Incorrect 17 ms 35540 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '214837477243'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 41704 KB Output is correct
2 Correct 30 ms 41756 KB Output is correct
3 Incorrect 63 ms 43744 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '20897672610412'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 44032 KB Output is correct
2 Correct 64 ms 45280 KB Output is correct
3 Correct 30 ms 41708 KB Output is correct
4 Correct 30 ms 41756 KB Output is correct
5 Runtime error 184 ms 105092 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -