Submission #172681

#	Time	Username	Problem	Language	Result	Execution time	Memory
172681		Ruxandra985	Boat (APIO16_boat)	C++14	100 / 100	999 ms	6600 KiB

boat

#include <bits/stdc++.h>
#define DIMN 510
#define MOD 1000000007
using namespace std;
pair <long long,long long> v[DIMN] , tot[2*DIMN];
long long dp[2*DIMN][DIMN] , op[DIMN] , last[DIMN] , fact[DIMN];
long long sum[DIMN][DIMN] , inv[DIMN];
void combinari (long long x , long long y){

    last[0] = 1;
    for (long long i = 1 ; i <= y && i <= x ; i++)
        last[i] = ((long long)last[i-1] * (x - i + 1)) % MOD;

}
long long ridput (long long x , long long y){
    long long sol = 1;

    while (y){

        if (y % 2)
            sol = ((long long) sol * x )%MOD;

        x = ((long long) x * x )%MOD;

        y/=2;
    }

    return sol;

}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    long long n , elem , open , i , j , k , left , toput;
    fscanf (fin,"%lld",&n);
    elem = 0;
    fact[0] = 1;
    inv[0] = 1;
    for (i=1;i<=n;i++){
        fscanf (fin,"%lld%lld",&v[i].first,&v[i].second);
        tot[++elem] = make_pair(v[i].first , i);
        tot[++elem] = make_pair(v[i].second + 1 , -i);
        fact[i] = ((long long) fact[i-1] * i )%MOD;
        inv[i] = ridput(fact[i] , MOD-2);
    }
    tot[++elem] = make_pair(1000000001 , 0);
    sort (tot + 1 , tot + elem + 1);
    dp[0][0] = 1;
    open = 0;
    int ant = 0;
    for (i=1;i<elem;i++){
        dp[i][0] = 1;
        /// vreau sa pun cateva in intervalul tot[i].first ... tot[i+1].first - 1
        if (tot[i].second > 0){ /// incepe ceva
            for (j = open + 1 ; ; j--){
                if (op[j-1] > tot[i].second)
                    op[j] = op[j-1];
                else {
                    op[j] = tot[i].second;
                    break;
                }
            }
            open++;
        }
        else { /// s a terminat ceva
            for (j = 1 ; j<open ; j++){
                if (op[j+1] > -tot[i].second)
                    op[j] = op[j+1];
            }
            op[open] = 0;
            open--;
        }
        if (tot[i+1].first == tot[i].first)
            continue;

        combinari (tot[i+1].first - tot[i].first , open);

        for (j=1;j<=open;j++){
            for (k=1;k<=j;k++){ /// sa pui k dintre j in interval
                 sum[j][k] = (sum[j][k-1] + ( (last[k] * inv[k])%MOD
                *( ( (fact[j-1] * inv[k-1] )%MOD * inv[j-k])%MOD)%MOD )%MOD )%MOD;

            }
        }

        for (j=1;j<=n;j++)
            dp[i][j] = dp[ant][j];

        /// ai updatat lista de disponibile
        for (j = 1 ; j <= open ; j++){ /// cea mai mare pe care o pun sigur
            left = j;
            for (k = 0 ; k <= op[j] ; k++){

                while (left && k >= op[j - left + 1]) /// sunt o(n) overall
                    left--;


                /// in interv curant pui cv subset intre opant[k] si op[j]
                /// pe k esti 100% sigura ca l ai pus

                toput = min(tot[i+1].first - tot[i].first , left);

                if (!toput)
                    break;

                /// poti sa pui intre 1 si toput in intervalul asta
                /// stii ca tu vrei neaparat sa il pui pe op[j]

                dp[i][op[j]] += ( dp[ant][k] * sum[left][toput] )%MOD;

                dp[i][op[j]] %= MOD;


            }
        }
        ant = i;
    }
    long long sol = 0;
    for (i=1;i<=n;i++)
        sol = (sol + dp[elem - 1][i])%MOD;
    fprintf (fout,"%lld",sol);
    return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:36:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%lld",&n);
     ~~~~~~~^~~~~~~~~~~~~~~
boat.cpp:41:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%lld%lld",&v[i].first,&v[i].second);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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