Submission #433852

#	Time	Username	Problem	Language	Result	Execution time	Memory
433852		JeanBombeur	Boat (APIO16_boat)	C++17	31 / 100	1454 ms	524292 KiB

boat

#include <iostream>
#include <cstdio>
#include <vector>
#define int long long
using namespace std;

//  <|°_°|>

const int MOD = (1000 * 1000 * 1000 + 7);
const int MAX_GROUPES = (501);

vector <int> DP[MAX_GROUPES];

pair <int, int> Bornes[MAX_GROUPES];

int nbGroupes;

void Read() {
	scanf("%lld", &nbGroupes);
	nbGroupes ++;
	for (int i = 1; i < nbGroupes; i ++)
	{
		scanf("%lld %lld", &Bornes[i].first, &Bornes[i].second);
		for (int j = Bornes[i].first; j <= Bornes[i].second; j ++)
		{
			DP[i].push_back(0);
		}
	}
	DP[0].push_back(1);
	return;
}

void Solve() {
	int sum = -1;
	for (int i = 0; i < nbGroupes; i ++)
	{
		int sz = DP[i].size();
		for (int k = 0; k < sz; k ++)
		{
			DP[i][k] %= MOD;
			sum += DP[i][k];
			if (k < sz - 1)
				DP[i][k + 1] += DP[i][k];
			for (int j = i + 1; j < nbGroupes; j ++)
			{
				if (Bornes[j].second > Bornes[i].first + k)
				{
					DP[j][max(0LL, Bornes[i].first + k + 1 - Bornes[j].first)] += DP[i][k];
				}
			}
		}
	}
	printf("%lld\n", sum % MOD);
	return;
}

signed main() {
	Read();
	Solve();
	return 0;
}

Compilation message (stderr)

boat.cpp: In function 'void Read()':
boat.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |  scanf("%lld", &nbGroupes);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~
boat.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |   scanf("%lld %lld", &Bornes[i].first, &Bornes[i].second);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42