Submission #45556

#	Time	Username	Problem	Language	Result	Execution time	Memory
45556		gnoor	Boat (APIO16_boat)	C++17	9 / 100	1189 ms	4488 KiB

boat

#include <cstdio>
#include <algorithm>
#include <map>

using namespace std;

map<int,int> mp;
int a[600];
int b[600];
int mod=1000000007;
int dec[1010];

long long dp[600][1010];

int main () {
	int n;
	scanf("%d",&n);
	for (int i=0;i<n;i++) {
		scanf("%d%d",&a[i],&b[i]);
		mp[a[i]-1];
		mp[b[i]];
	}
	int i=1;
	for (auto &ii:mp) {
		dec[i]=ii.first;
		ii.second=i++;
	}
	for (int i=0;i<n;i++) {
		a[i]=mp[a[i]-1];
		b[i]=mp[b[i]];
	}
	int nn=mp.size();

	for (int i=0;i<n;i++) {
		//printf("** %d %d\n",a[i],b[i]);
		for (int j=i-1;j>=0;j--) {
			for (int k=a[i]+1;k<=b[i];k++) {
				//printf("** %d %d %d %lld\n",i,j,k,dp[j][k-1]);
				dp[i][k]+=dp[j][k-1]*(dec[k]-dec[k-1]);
				dp[i][k]%=mod;
				if (k>a[j]&&k<=b[j]) {
					dp[i][k]+=(long long)(dec[k]-dec[k-1])*(dec[k]-dec[k-1]-1)/2;
				}
				dp[i][k]%=mod;
			}
		}
		for (int k=a[i]+1;k<=b[i];k++) {
			dp[i][k]+=(dec[k]-dec[k-1]);
			dp[i][k]+=dp[i][k-1];
			dp[i][k]%=mod;
		}
		for (int k=b[i]+1;k<=nn;k++) {
			dp[i][k]+=dp[i][k-1];
			dp[i][k]%=mod;
		}
		//for (int k=1;k<=nn;k++) {
			//printf("%lld ",dp[i][k]);
		//}
		//printf("\n");
	}
	long long ans=0;
	for (int i=0;i<n;i++) {
		ans+=dp[i][nn];
		ans%=mod;
	}
	printf("%lld\n",ans);
	return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
boat.cpp:19: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