oj.uz

Submission #255697

# Submission time Handle Problem Language Result Execution time Memory
255697 2020-08-01T15:32:05 Z Mercenary Boat (APIO16_boat) C++14
0 / 100
 250 ms 4472 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef double ld;
typedef pair<int,int> ii;
typedef tree <ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int maxn = 500 + 5;
const int mod = 1e9 + 7;

int n , a[maxn] , b[maxn];
int dp[maxn][maxn * 2];
int c[maxn * 2][maxn];
vector<int> val;
int Pow(int i , int j){
    if(j == 0)return 1;
    int r = Pow(i , j / 2);
    if(j & 1)return (ll)r * r % mod * i % mod;
    return (ll)r * r % mod;
}
int r[maxn];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    cin >> n;
    for(int i = 1 ; i <= n ; ++i){
        cin >> a[i] >> b[i];--a[i];
        val.pb(a[i]);val.pb(b[i]);
        r[i] = Pow(i , mod - 2);
    }
    sort(val.begin(),val.end());val.erase(unique(val.begin(),val.end()),val.end());
    for(int i = 0 ; i < val.size() ; ++i){
        dp[0][i] = 1;
        if(i > 0){
            int len = val[i] - val[i - 1];
            c[i][0] = 1;
            for(int j = 1 ; j <= n ; ++j){
                c[i][j] = c[i][j - 1] * (len + j - 1) % mod * r[j] % mod;
            }
        }
    }
    for(int i = 1 ; i <= n ; ++i){
        dp[i][0] = 1;
        for(int j = 1 ; j < val.size() ; ++j){
            int sum = 0;
            dp[i][j] = dp[i][j - 1];
            for(int k = i ; k >= 1 ; --k){
                if(a[k] < val[j] && val[j] <= b[k]){
                    dp[i][j] = (dp[i][j] + (ll)dp[k - 1][j - 1] * c[j][++sum]) %mod;
                }
            }
//            cout << dp[i][j] << " ";
        }
//        cout << endl;
    }
    cout << dp[n][val.size() - 1] - 1;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:46:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < val.size() ; ++i){
                     ~~^~~~~~~~~~~~
boat.cpp:58:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 1 ; j < val.size() ; ++j){
                         ~~^~~~~~~~~~~~
boat.cpp:36:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
boat.cpp:37:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 4344 KB Output is correct
2 Correct 250 ms 4344 KB Output is correct
3 Correct 249 ms 4344 KB Output is correct
4 Correct 247 ms 4388 KB Output is correct
5 Correct 243 ms 4404 KB Output is correct
6 Correct 154 ms 4344 KB Output is correct
7 Correct 150 ms 4348 KB Output is correct
8 Correct 152 ms 4344 KB Output is correct
9 Correct 158 ms 4344 KB Output is correct
10 Correct 158 ms 4344 KB Output is correct
11 Correct 152 ms 4344 KB Output is correct
12 Correct 159 ms 4360 KB Output is correct
13 Correct 153 ms 4344 KB Output is correct
14 Correct 144 ms 4472 KB Output is correct
15 Correct 155 ms 4344 KB Output is correct
16 Incorrect 56 ms 2680 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 4344 KB Output is correct
2 Correct 250 ms 4344 KB Output is correct
3 Correct 249 ms 4344 KB Output is correct
4 Correct 247 ms 4388 KB Output is correct
5 Correct 243 ms 4404 KB Output is correct
6 Correct 154 ms 4344 KB Output is correct
7 Correct 150 ms 4348 KB Output is correct
8 Correct 152 ms 4344 KB Output is correct
9 Correct 158 ms 4344 KB Output is correct
10 Correct 158 ms 4344 KB Output is correct
11 Correct 152 ms 4344 KB Output is correct
12 Correct 159 ms 4360 KB Output is correct
13 Correct 153 ms 4344 KB Output is correct
14 Correct 144 ms 4472 KB Output is correct
15 Correct 155 ms 4344 KB Output is correct
16 Incorrect 56 ms 2680 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 4344 KB Output is correct
2 Correct 250 ms 4344 KB Output is correct
3 Correct 249 ms 4344 KB Output is correct
4 Correct 247 ms 4388 KB Output is correct
5 Correct 243 ms 4404 KB Output is correct
6 Correct 154 ms 4344 KB Output is correct
7 Correct 150 ms 4348 KB Output is correct
8 Correct 152 ms 4344 KB Output is correct
9 Correct 158 ms 4344 KB Output is correct
10 Correct 158 ms 4344 KB Output is correct
11 Correct 152 ms 4344 KB Output is correct
12 Correct 159 ms 4360 KB Output is correct
13 Correct 153 ms 4344 KB Output is correct
14 Correct 144 ms 4472 KB Output is correct
15 Correct 155 ms 4344 KB Output is correct
16 Incorrect 56 ms 2680 KB Output isn't correct
17 Halted 0 ms 0 KB -