제출 #172131

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
172131		Ruxandra985	Boat (APIO16_boat)	C++14	9 / 100	52 ms	2452 KiB

boat

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

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

}
int ridput (int x , int y){
    int 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;
    int n , elem , open , i , j , k , sol;
    fscanf (fin,"%d",&n);
    elem = 0;
    fact[0] = 1;
    for (i=1;i<=n;i++){
        fscanf (fin,"%d%d",&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;
    }
    tot[++elem] = make_pair(1000000001 , 0);
    sort (tot + 1 , tot + elem + 1);
    open = 0;
    for (i=1;i<elem;i++){
        /// 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];
            }
            open--;
        }
        combinari (tot[i+1].first - tot[i].first , open);

        /// ai updatat lista de disponibile
        for (j = 1 ; j <= open ; j++){
            for (k = j ; k <= open ; k++){
                if (k != j && op[k] != op[k-1] + 1){ /// cumva nu vin in ord exacta
                    break;
                }
                if (k - j + 1 > tot[i+1].first - tot[i].first)
                    break; /// nu poti fizic sa pui atatea
                /// intre j si k e un interval compact pe care il voi pune aici
                dp[i][op[k]] += (((long long)(dp[i-1][op[j]-1] + 1)* last[k - j + 1])%MOD * ridput(fact[k - j + 1] , MOD-2))%MOD;
                dp[i][op[k]] %=MOD;
                /// + 1 pt ca luam in calcul cazul cand adaugam intervalul asta la
                /// multimea vida
            }
        }
        for (j=1;j<=n;j++){
            dp[i+1][j] = dp[i][j];
            dp[i][j] = (dp[i][j] + dp[i][j-1]) % MOD;
        }
    }
    fprintf (fout,"%d",dp[elem-1][n]);
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

boat.cpp: In function 'int main()':
boat.cpp:34:39: warning: unused variable 'sol' [-Wunused-variable]
     int n , elem , open , i , j , k , sol;
                                       ^~~
boat.cpp:35:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d",&n);
     ~~~~~~~^~~~~~~~~~~~~
boat.cpp:39:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d%d",&v[i].first,&v[i].second);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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