oj.uz

Submission #61152

# Submission time Handle Problem Language Result Execution time Memory
61152 2018-07-25T09:04:37 Z Eae02 Boat (APIO16_boat) C++14
0 / 100
 9 ms 812 KB 
#include <bits/stdc++.h>
	
uint64_t PRIME = 1000000007;
	
std::vector<std::pair<uint64_t, uint64_t>> schools;
	
std::unordered_map<uint64_t, uint64_t> memo[500];
	
uint64_t count(int i, uint64_t min)
{
	if (i >= schools.size())
		return 1;
	auto mIt = memo[i].find(min);
	if (mIt != memo[i].end())
		return mIt->second;
	
	uint64_t c = count(i + 1, min);
	for (uint64_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));
	return c;
}

int64_t negMod(int64_t x)
{
	int64_t r = x % PRIME;
	return r < 0 ? (r + PRIME) : r;
}

int main()
{
	int N;
	std::cin >> N;
	
	bool allSame = true;
	uint64_t max2 = 0;
	
	schools.resize(N);
	for (int i = 0; i < N; i++)
	{
		std::cin >> schools[i].first;
		std::cin >> schools[i].second;
		if (schools[i].first != schools[i].second)
			allSame = false;
		max2 = std::max(max2, schools[i].second);
	}
	
	/*if (allSame)
	{
		std::cout << (count(0, 0) - 1) << std::endl;
	}
	else
	{*/
		std::vector<int64_t> waysElim(max2 + 1);
		int64_t ways = 1;
		for (int i = 0; i < N; i++)
		{
			const int64_t prevWays = ways;
			
			const int64_t d = schools[i].second - schools[i].first + 1;
			ways = (ways * ((d + 1) % PRIME)) % PRIME;
			
			for (int64_t j = 0; j < d; j++)
			{
				int64_t eI = schools[i].second - j;
				ways = negMod(ways - waysElim[eI]);
				waysElim[eI] = negMod(((j + 1) % PRIME) * prevWays - waysElim[eI]);
			}
		}
		std::cout << negMod(ways - 1) << std::endl;
	//}
}

Compilation message

boat.cpp: In function 'uint64_t count(int, uint64_t)':
boat.cpp:11:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (i >= schools.size())
      ~~^~~~~~~~~~~~~~~~~
boat.cpp: In function 'int main()':
boat.cpp:38:7: warning: variable 'allSame' set but not used [-Wunused-but-set-variable]
  bool allSame = true;
       ^~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 760 KB Execution killed with signal 11 (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 9 ms 760 KB Execution killed with signal 11 (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 Runtime error 7 ms 812 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

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