답안 #47294 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
47294	2018-04-30T09:49:33 Z	ngkan146	Boat (APIO16_boat)	C++11	36 / 100	2000 ms	6260 KB

boat

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = (ll) 1e9+7;
int n, a[505], b[505];
ll f[505][3005];
ll g[505];
ll fact[505], inv[505];
ll Ckn(int x,int y){
    return fact[y] * inv[x] % mod * inv[y-x] % mod;
}
ll mod_inverse(ll a){
    ll r1 = a, r2 = mod, x1 = 1,x2 = 0, q, tmp;
    while(r2 != 0){
        q = r1 / r2;
        tmp = x1 -  q * x2;
        x1 = x2;
        x2 = tmp;
        tmp = r1 % r2;
        r1 = r2;
        r2 = tmp;
    }
    return (x1+mod)%mod;
}
int main(){
    fact[0] = 1;
    for(int i=1;i<=500;i++)
        fact[i] = fact[i-1] * i % mod;
    for(int i=0;i<=500;i++)
        inv[i] = mod_inverse(fact[i]);

    //freopen("2_11.in","r",stdin);
    iostream::sync_with_stdio(0);
    cin >> n;
    vector <int> lst;
    for(int i=1;i<=n;i++)
        cin >> a[i] >> b[i],
        lst.push_back(a[i]),
        lst.push_back(b[i]);
    sort(lst.begin(), lst.end());
    lst.resize(unique(lst.begin(),lst.end()) - lst.begin());
    vector <pair<int,int> > range;
    for(int i=0;i<lst.size();i++){
        range.push_back({lst[i], lst[i]});
        if (i != lst.size() - 1 && lst[i]+1 <= lst[i+1]-1)
            range.push_back({lst[i]+1, lst[i+1]-1});
    }
    //range.clear();  for(int i=1;i<=n;i++) range.push_back({i,i});
    range.insert(range.begin(), {-1,-1});
    g[0] = 1;

    ll ans = 0;
    for(int j = 1;j < range.size();j ++){
        // f[i][j] = cnt of way that end at i and value of i in range j
        int len = range[j].second - range[j].first + 1;
        ll arr[505], sumG[505];
        arr[0] = 1;
        sumG[0] = g[0];
        for(int i=1;i<=n;i++)
            sumG[i] = (sumG[i-1] + g[i]) % mod,
            arr[i] = arr[i-1] * (len+1-i) % mod;

        for(int i=1;i<=n;i++){
            if (!(a[i] <= range[j].first && range[j].second <= b[i]))    continue;

            int possiBoat = 0;
            ll tmp = 0;

            for(int ii=i;ii>=1;ii--){
                if (!(a[ii] <= range[j].first && range[j].second <= b[ii]))  continue;
                possiBoat++;
                if (possiBoat == 1){
                    f[i][j] = (f[i][j] + sumG[ii-1] * arr[possiBoat] % mod) % mod;
                }
                else{
                    for(int k=2;k<=min(len, possiBoat);k++){
                        f[i][j] = (f[i][j] + sumG[ii-1] * Ckn(k-2, possiBoat-2) % mod * arr[k] % mod * inv[k] % mod) % mod;
                    }
                }
            }
            ans = (ans + f[i][j]) % mod;
        }
        for(int i=0;i<=n;i++){
            g[i] = (g[i] + f[i][j]) % mod;
        }
    }
//    for(int j=1;j<range.size();j++){
//        for(int i=1;i<=n;i++)
//            cout << f[i][j] << ' ';
//        cout << endl;
//    }
    cout << ans;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:43:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<lst.size();i++){
                 ~^~~~~~~~~~~
boat.cpp:45:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i != lst.size() - 1 && lst[i]+1 <= lst[i+1]-1)
             ~~^~~~~~~~~~~~~~~~~
boat.cpp:53:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 1;j < range.size();j ++){
                   ~~^~~~~~~~~~~~~~
boat.cpp:67:16: warning: unused variable 'tmp' [-Wunused-variable]
             ll tmp = 0;
                ^~~

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	2424 KB	Output is correct
2	Correct	12 ms	2424 KB	Output is correct
3	Correct	12 ms	2596 KB	Output is correct
4	Correct	12 ms	2596 KB	Output is correct
5	Correct	15 ms	2644 KB	Output is correct
6	Correct	11 ms	2800 KB	Output is correct
7	Correct	11 ms	2800 KB	Output is correct
8	Correct	11 ms	2800 KB	Output is correct
9	Correct	11 ms	2800 KB	Output is correct
10	Correct	13 ms	2800 KB	Output is correct
11	Correct	14 ms	2800 KB	Output is correct
12	Correct	11 ms	2800 KB	Output is correct
13	Correct	12 ms	2800 KB	Output is correct
14	Correct	11 ms	2868 KB	Output is correct
15	Correct	12 ms	2868 KB	Output is correct
16	Correct	6 ms	2868 KB	Output is correct
17	Correct	6 ms	2932 KB	Output is correct
18	Correct	6 ms	2968 KB	Output is correct
19	Correct	6 ms	2968 KB	Output is correct
20	Correct	6 ms	2968 KB	Output is correct

Subtask #2
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	2424 KB	Output is correct
2	Correct	12 ms	2424 KB	Output is correct
3	Correct	12 ms	2596 KB	Output is correct
4	Correct	12 ms	2596 KB	Output is correct
5	Correct	15 ms	2644 KB	Output is correct
6	Correct	11 ms	2800 KB	Output is correct
7	Correct	11 ms	2800 KB	Output is correct
8	Correct	11 ms	2800 KB	Output is correct
9	Correct	11 ms	2800 KB	Output is correct
10	Correct	13 ms	2800 KB	Output is correct
11	Correct	14 ms	2800 KB	Output is correct
12	Correct	11 ms	2800 KB	Output is correct
13	Correct	12 ms	2800 KB	Output is correct
14	Correct	11 ms	2868 KB	Output is correct
15	Correct	12 ms	2868 KB	Output is correct
16	Correct	6 ms	2868 KB	Output is correct
17	Correct	6 ms	2932 KB	Output is correct
18	Correct	6 ms	2968 KB	Output is correct
19	Correct	6 ms	2968 KB	Output is correct
20	Correct	6 ms	2968 KB	Output is correct
21	Correct	1219 ms	5372 KB	Output is correct
22	Correct	1208 ms	5372 KB	Output is correct
23	Correct	1033 ms	5372 KB	Output is correct
24	Correct	1271 ms	5372 KB	Output is correct
25	Correct	1312 ms	5372 KB	Output is correct
26	Correct	1993 ms	6244 KB	Output is correct
27	Correct	1973 ms	6260 KB	Output is correct
28	Correct	1969 ms	6260 KB	Output is correct
29	Execution timed out	2043 ms	6260 KB	Time limit exceeded
30	Halted	0 ms	0 KB	-

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	39 ms	6260 KB	Output is correct
2	Correct	24 ms	6260 KB	Output is correct
3	Correct	37 ms	6260 KB	Output is correct
4	Correct	39 ms	6260 KB	Output is correct
5	Correct	48 ms	6260 KB	Output is correct
6	Correct	155 ms	6260 KB	Output is correct
7	Correct	170 ms	6260 KB	Output is correct
8	Correct	152 ms	6260 KB	Output is correct
9	Correct	157 ms	6260 KB	Output is correct
10	Correct	154 ms	6260 KB	Output is correct
11	Correct	47 ms	6260 KB	Output is correct
12	Correct	35 ms	6260 KB	Output is correct
13	Correct	39 ms	6260 KB	Output is correct
14	Correct	36 ms	6260 KB	Output is correct
15	Correct	48 ms	6260 KB	Output is correct
16	Correct	22 ms	6260 KB	Output is correct
17	Correct	17 ms	6260 KB	Output is correct
18	Correct	18 ms	6260 KB	Output is correct
19	Correct	18 ms	6260 KB	Output is correct
20	Correct	23 ms	6260 KB	Output is correct

Subtask #4
0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	2424 KB	Output is correct
2	Correct	12 ms	2424 KB	Output is correct
3	Correct	12 ms	2596 KB	Output is correct
4	Correct	12 ms	2596 KB	Output is correct
5	Correct	15 ms	2644 KB	Output is correct
6	Correct	11 ms	2800 KB	Output is correct
7	Correct	11 ms	2800 KB	Output is correct
8	Correct	11 ms	2800 KB	Output is correct
9	Correct	11 ms	2800 KB	Output is correct
10	Correct	13 ms	2800 KB	Output is correct
11	Correct	14 ms	2800 KB	Output is correct
12	Correct	11 ms	2800 KB	Output is correct
13	Correct	12 ms	2800 KB	Output is correct
14	Correct	11 ms	2868 KB	Output is correct
15	Correct	12 ms	2868 KB	Output is correct
16	Correct	6 ms	2868 KB	Output is correct
17	Correct	6 ms	2932 KB	Output is correct
18	Correct	6 ms	2968 KB	Output is correct
19	Correct	6 ms	2968 KB	Output is correct
20	Correct	6 ms	2968 KB	Output is correct
21	Correct	1219 ms	5372 KB	Output is correct
22	Correct	1208 ms	5372 KB	Output is correct
23	Correct	1033 ms	5372 KB	Output is correct
24	Correct	1271 ms	5372 KB	Output is correct
25	Correct	1312 ms	5372 KB	Output is correct
26	Correct	1993 ms	6244 KB	Output is correct
27	Correct	1973 ms	6260 KB	Output is correct
28	Correct	1969 ms	6260 KB	Output is correct
29	Execution timed out	2043 ms	6260 KB	Time limit exceeded
30	Halted	0 ms	0 KB	-

답안 #47294

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 0 / 22.0

Subtask #3 27.0 / 27.0

Subtask #4 0 / 42.0

Subtask #1
9.0 / 9.0

Subtask #2
0 / 22.0

Subtask #3
27.0 / 27.0

Subtask #4
0 / 42.0