Submission #105722

#	Time	Username	Problem	Language	Result	Execution time	Memory
105722		Pro_ktmr	Boat (APIO16_boat)	C++14	9 / 100	16 ms	4268 KiB

boat

#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define PB push_back
#define MP make_pair
#define MOD 1000000007

int N;
int a[500],b[500];
vector<int> zaatu;

LL dp[500][1001] = {};
LL solve(int now, int bef){
	if(now == N) return 1LL;
	if(dp[now][bef] != 0) return dp[now][bef];
	LL ans = solve(now+1,bef);
	if(zaatu[bef] < a[now]) ans += solve(now+1,lower_bound(zaatu.begin(), zaatu.end(), a[now])-zaatu.begin());
	return dp[now][bef] = ans % MOD;
}

int main(){
	
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		scanf("%d%d", a+i, b+i);
		b[i]++;
		zaatu.PB(a[i]);
		zaatu.PB(b[i]);
	}
	zaatu.PB(0);
	sort(zaatu.begin(), zaatu.end());

	cout << solve(0, 0) - 1 << endl;

}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
boat.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", a+i, b+i);
   ~~~~~^~~~~~~~~~~~~~~~~~

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