Submission #760538

#	Time	Username	Problem	Language	Result	Execution time	Memory
760538		Username4132	Boat (APIO16_boat)	C++14	36 / 100	2019 ms	2772 KiB

boat

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using ll = long long;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define PB push_back

const int MAXN=510, MOD=1000000007;
int n, le[MAXN], ri[MAXN], arr[2*MAXN][MAXN];
bool adj[2*MAXN][MAXN];
vector<int> pt;

ll ex(ll b, int e){
    ll ret=1;
    while(e>0){
        if(e&1) ret=(ret*b)%MOD;
        b = (b*b)%MOD;
        e>>=1;
    }
    return ret;
}

int main(){
    scanf("%d", &n);
    forn(i, n) scanf("%d %d", le+i, ri+i), pt.PB(le[i]), pt.PB(ri[i]+1);
    sort(pt.begin(), pt.end());
    pt.erase(unique(pt.begin(), pt.end()), pt.end());
    forn(i, n){
        auto itr = lower_bound(pt.begin(),  pt.end(), le[i]);
        for(; itr!=pt.end() && (*itr)<=ri[i]; ++itr) adj[itr-pt.begin()][i]=true;
    }
    forn(i, pt.size()-1){
        forn(j, n){
            arr[i+1][j]=(arr[i][j]-(j==0? 0 : arr[i][j-1]) + MOD)%MOD;
            if(adj[i][j]){
                int cnt=0, m=pt[i+1]-pt[i];
                ll comb=m;
                dforn(k, j){
                    int dif = (arr[i][k] - (k==0? 0 : arr[i][k-1]) + MOD)%MOD;
                    arr[i+1][j]=(arr[i+1][j] + comb*dif)%MOD;
                    if(adj[i][k]){
                        ++cnt;
                        comb=(((comb*(m+cnt))%MOD)*ex(cnt+1, MOD-2))%MOD;
                    }
                }
                arr[i+1][j]=(arr[i+1][j]+comb)%MOD;
            }
        }
        forn(j, n-1) arr[i+1][j+1]=(arr[i+1][j+1]+arr[i+1][j])%MOD;
    }
    printf("%d\n", arr[pt.size()-1][n-1]);
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
boat.cpp:27:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     forn(i, n) scanf("%d %d", le+i, ri+i), pt.PB(le[i]), pt.PB(ri[i]+1);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~

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