oj.uz

Submission #645826

# Submission time Handle Problem Language Result Execution time Memory
645826 2022-09-28T06:23:03 Z ymm Catfish Farm (IOI22_fish) C++17
6 / 100
 159 ms 74180 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 = 600'010;
ll dpu[N*2], dpd[N*2];
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(m, 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:34:2: note: in expansion of macro 'Loop'
   34 |  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:37:2: note: in expansion of macro 'Loop'
   37 |  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:55:2: note: in expansion of macro 'Loop'
   55 |  Loop (i,1,C[1].size()) {
      |  ^~~~
fish.cpp:58: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]
   58 |   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:76:3: note: in expansion of macro 'Loop'
   76 |   Loop (i,1,C[c].size()) {
      |   ^~~~
fish.cpp:79: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]
   79 |    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 49 ms 25884 KB Output is correct
2 Correct 55 ms 27652 KB Output is correct
3 Correct 20 ms 22972 KB Output is correct
4 Correct 20 ms 23040 KB Output is correct
5 Runtime error 159 ms 74180 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 7 ms 14412 KB Output is correct
2 Correct 79 ms 29664 KB Output is correct
3 Correct 94 ms 32420 KB Output is correct
4 Correct 48 ms 25924 KB Output is correct
5 Correct 56 ms 27676 KB Output is correct
6 Correct 8 ms 14352 KB Output is correct
7 Correct 7 ms 14292 KB Output is correct
8 Correct 10 ms 14284 KB Output is correct
9 Correct 7 ms 14292 KB Output is correct
10 Correct 20 ms 22972 KB Output is correct
11 Correct 20 ms 22972 KB Output is correct
12 Correct 47 ms 25860 KB Output is correct
13 Correct 57 ms 27668 KB Output is correct
14 Correct 49 ms 25956 KB Output is correct
15 Correct 54 ms 27216 KB Output is correct
16 Correct 50 ms 25856 KB Output is correct
17 Correct 56 ms 27180 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 22968 KB Output is correct
2 Correct 20 ms 23024 KB Output is correct
3 Incorrect 41 ms 25276 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 7 ms 14292 KB Output is correct
2 Correct 8 ms 14300 KB Output is correct
3 Correct 7 ms 14292 KB Output is correct
4 Correct 7 ms 14404 KB Output is correct
5 Correct 7 ms 14292 KB Output is correct
6 Correct 7 ms 14292 KB Output is correct
7 Correct 8 ms 14292 KB Output is correct
8 Correct 8 ms 14396 KB Output is correct
9 Incorrect 8 ms 14444 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 7 ms 14292 KB Output is correct
2 Correct 8 ms 14300 KB Output is correct
3 Correct 7 ms 14292 KB Output is correct
4 Correct 7 ms 14404 KB Output is correct
5 Correct 7 ms 14292 KB Output is correct
6 Correct 7 ms 14292 KB Output is correct
7 Correct 8 ms 14292 KB Output is correct
8 Correct 8 ms 14396 KB Output is correct
9 Incorrect 8 ms 14444 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 7 ms 14292 KB Output is correct
2 Correct 8 ms 14300 KB Output is correct
3 Correct 7 ms 14292 KB Output is correct
4 Correct 7 ms 14404 KB Output is correct
5 Correct 7 ms 14292 KB Output is correct
6 Correct 7 ms 14292 KB Output is correct
7 Correct 8 ms 14292 KB Output is correct
8 Correct 8 ms 14396 KB Output is correct
9 Incorrect 8 ms 14444 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 20 ms 22968 KB Output is correct
2 Correct 20 ms 23024 KB Output is correct
3 Incorrect 41 ms 25276 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 49 ms 25884 KB Output is correct
2 Correct 55 ms 27652 KB Output is correct
3 Correct 20 ms 22972 KB Output is correct
4 Correct 20 ms 23040 KB Output is correct
5 Runtime error 159 ms 74180 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -