Submission #36802

#	Time	Username	Problem	Language	Result	Execution time	Memory
36802		imaxblue	Boat (APIO16_boat)	C++14	100 / 100	1109 ms	26252 KiB

boat

#include <iostream>
#include<map>
#include<cstdio>
#include<set>
using namespace std;
#define MN 1000000007
#define mult(a, b) a*1LL*b%MN
#define x first
#define ll long long
#define ub upper_bound
#define y second

short l2, l3,n, p, c;
bool k[505][1005];
int a[505], b[505], rev[1005], ncr2[1005][505];
ll ans, dp[1005][1005], t[1005][1005],
    ncr[1005][505], ncrt[505][505], cnt[1005];
map<int, short> m;
//set<int> s;
int main() {
	cin >> n;
	for (short l=1; l<=n; ++l){
		scanf("%i%i", &a[l], &b[l]); b[l]++;
		if (m.count(a[l])==0) m[a[l]]=0;
		if (m.count(b[l])==0) m[b[l]]=0;
		m[a[l]]++; m[b[l]]--; //s.insert(a[l]); s.insert(b[l]);
	}
	for (auto i:m){
	    c+=i.y;
        rev[m[i.x]=++p]=i.x;
        cnt[p]=c;
	}
	c=0;
	for (short l=1; l<m.size(); ++l){
		ncr[l][0]=1;
		for (l2=1; l2<=cnt[l]; ++l2){
            if (l2>rev[l+1]-rev[l]+1) break;
			ncr[l][l2]=(ncr[l][l2-1]*(rev[l+1]-rev[l]+1-l2))%MN;
			while(ncr[l][l2]%l2) ncr[l][l2]+=MN;
			ncr[l][l2]=(ncr[l][l2]/l2)%MN;
		}
	}
	for (short l=0; l<=500; ++l){
        ncrt[l][0]=1;
        for (l2=1; l2<=l; ++l2){
            ncrt[l][l2]=(ncrt[l][l2-1]*(l+1-l2))%MN;
			while(ncrt[l][l2]%l2) ncrt[l][l2]+=MN;
			ncrt[l][l2]=(ncrt[l][l2]/l2)%MN;
        }
	}
	for (short l=1; l<m.size(); ++l){
        for (l2=2; l2<=cnt[l]; ++l2){
            for (l3=2; l3<=l2; ++l3){
                ncr2[l][l2]=(ncr2[l][l2]+ncr[l][l3]*ncrt[l2-2][l3-2])%MN;
            }
        }
	}
	for (short l=1; l<=n; ++l){
		a[l]=m[a[l]]; b[l]=m[b[l]];
		for (l2=1; l2<a[l]; ++l2){
			t[l][l2]=(t[l-1][l2]+t[l][l2-1]-t[l-1][l2-1])%MN;
			if (t[l][l2]<0) t[l][l2]+=MN;
		}
		for (l2=a[l]; l2<b[l]; ++l2){
            c=k[l][l2]=1;
			dp[l][l2]=(dp[l][l2]+(t[l-1][l2-1]+1)*ncr[l2][1])%MN;
			//cout << dp[l][l2] << ' ' ;
			for (l3=l-1; l3>0; --l3){
				if (k[l3][l2])
				dp[l][l2]=(dp[l][l2]+(t[l3-1][l2-1]+1)*ncr2[l2][++c])%MN;
			}
			t[l][l2]=(t[l-1][l2]+t[l][l2-1]-t[l-1][l2-1]+dp[l][l2])%MN;
			ans=(ans+dp[l][l2])%MN;
		}
		for (l2=b[l]; l2<m.size(); ++l2){
			t[l][l2]=(t[l-1][l2]+t[l][l2-1]-t[l-1][l2-1])%MN;
			if (t[l][l2]<0) t[l][l2]+=MN;
			//cout << t[l][l2] << ' ';
		}
		//cout << endl;
	}
	cout << ans;
	return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:34:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (short l=1; l<m.size(); ++l){
                   ^
boat.cpp:51:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (short l=1; l<m.size(); ++l){
                   ^
boat.cpp:75:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (l2=b[l]; l2<m.size(); ++l2){
                   ^
boat.cpp:23:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i%i", &a[l], &b[l]); b[l]++;
                              ^

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