oj.uz

Submission #172131

# Submission time Handle Problem Language Result Execution time Memory
172131 2019-12-31T10:19:19 Z Ruxandra985 Boat (APIO16_boat) C++14
9 / 100
 52 ms 2452 KB 
#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;
}

Compilation message

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2424 KB Output is correct
2 Correct 7 ms 2296 KB Output is correct
3 Correct 7 ms 2296 KB Output is correct
4 Correct 7 ms 2296 KB Output is correct
5 Correct 7 ms 2424 KB Output is correct
6 Correct 7 ms 2452 KB Output is correct
7 Correct 7 ms 2296 KB Output is correct
8 Correct 7 ms 2424 KB Output is correct
9 Correct 7 ms 2428 KB Output is correct
10 Correct 7 ms 2424 KB Output is correct
11 Correct 7 ms 2332 KB Output is correct
12 Correct 7 ms 2424 KB Output is correct
13 Correct 7 ms 2424 KB Output is correct
14 Correct 7 ms 2424 KB Output is correct
15 Correct 7 ms 2424 KB Output is correct
16 Correct 7 ms 2172 KB Output is correct
17 Correct 7 ms 2424 KB Output is correct
18 Correct 7 ms 2424 KB Output is correct
19 Correct 7 ms 2296 KB Output is correct
20 Correct 7 ms 2296 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2424 KB Output is correct
2 Correct 7 ms 2296 KB Output is correct
3 Correct 7 ms 2296 KB Output is correct
4 Correct 7 ms 2296 KB Output is correct
5 Correct 7 ms 2424 KB Output is correct
6 Correct 7 ms 2452 KB Output is correct
7 Correct 7 ms 2296 KB Output is correct
8 Correct 7 ms 2424 KB Output is correct
9 Correct 7 ms 2428 KB Output is correct
10 Correct 7 ms 2424 KB Output is correct
11 Correct 7 ms 2332 KB Output is correct
12 Correct 7 ms 2424 KB Output is correct
13 Correct 7 ms 2424 KB Output is correct
14 Correct 7 ms 2424 KB Output is correct
15 Correct 7 ms 2424 KB Output is correct
16 Correct 7 ms 2172 KB Output is correct
17 Correct 7 ms 2424 KB Output is correct
18 Correct 7 ms 2424 KB Output is correct
19 Correct 7 ms 2296 KB Output is correct
20 Correct 7 ms 2296 KB Output is correct
21 Incorrect 52 ms 2296 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2424 KB Output is correct
2 Correct 7 ms 2296 KB Output is correct
3 Correct 7 ms 2296 KB Output is correct
4 Correct 7 ms 2296 KB Output is correct
5 Correct 7 ms 2424 KB Output is correct
6 Correct 7 ms 2452 KB Output is correct
7 Correct 7 ms 2296 KB Output is correct
8 Correct 7 ms 2424 KB Output is correct
9 Correct 7 ms 2428 KB Output is correct
10 Correct 7 ms 2424 KB Output is correct
11 Correct 7 ms 2332 KB Output is correct
12 Correct 7 ms 2424 KB Output is correct
13 Correct 7 ms 2424 KB Output is correct
14 Correct 7 ms 2424 KB Output is correct
15 Correct 7 ms 2424 KB Output is correct
16 Correct 7 ms 2172 KB Output is correct
17 Correct 7 ms 2424 KB Output is correct
18 Correct 7 ms 2424 KB Output is correct
19 Correct 7 ms 2296 KB Output is correct
20 Correct 7 ms 2296 KB Output is correct
21 Incorrect 52 ms 2296 KB Output isn't correct
22 Halted 0 ms 0 KB -