oj.uz

Submission #61126

# Submission time Handle Problem Language Result Execution time Memory
61126 2018-07-25T08:29:41 Z Eae02 Boat (APIO16_boat) C++14
0 / 100
 2000 ms 525312 KB 
#include <bits/stdc++.h>

uint64_t PRIME = 1000000007;

std::vector<std::pair<uint32_t, uint32_t>> schools;

//std::unordered_map<uint64_t, uint64_t> memo[500];
//uint64_t memo[500][1000000000];

uint32_t* memo[500];

uint32_t count(int i, uint32_t min)
{
	if (i >= schools.size())
		return 1;
	//auto mIt = memo[i].find(min);
	//if (mIt != memo[i].end())
	//	return mIt->second;
	
	if (memo[i][min] != 0)
		return memo[i][min] - 1;
	
	uint32_t c = count(i + 1, min);
	for (uint32_t n = std::max(schools[i].first, min == 0 ? 0 : (min + 1)); n <= schools[i].second; n++)
	{
		c = (c + count(i + 1, n)) % PRIME;
	}
	
	//memo[i].insert(std::make_pair(min, c));
	memo[i][min] = c + 1;
	return c;
}

int main()
{
	int N;
	std::cin >> N;
	
	uint32_t max2 = 0;
	
	schools.resize(N);
	for (int i = 0; i < N; i++)
	{
		std::cin >> schools[i].first;
		std::cin >> schools[i].second;
		max2 = std::max(max2, schools[i].second);
	}
	
	for (int i = 0; i < N; i++)
	{
		memo[i] = (uint32_t*)calloc(max2 + 1, sizeof(uint32_t));
	}
	
	std::cout << (count(0, 0) - 1) << std::endl;
}

Compilation message

boat.cpp: In function 'uint32_t count(int, uint32_t)':
boat.cpp:14:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (i >= schools.size())
      ~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 1245 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 1245 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2058 ms 525312 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Runtime error 1245 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -