답안 #47153 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
47153	2018-04-28T07:39:13 Z	PowerOfNinjaGo	Boat (APIO16_boat)	C++17	36 / 100	2000 ms	8548 KB

boat

//Power Of Ninja Go
#include <bits/stdc++.h>
//#ifdef atom #else #endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector< ii > vii;
#define X first
#define Y second
#define pb push_back
const int maxn = 505;
const int md = 1e9+7;
void add(int &a, int b)
{
    a += b;
    if(a>= md) a-= md;
}
int mul(int a, int b)
{
    return (1LL*a*b)%md;
}
int expo(int a, int b)
{
    if(b == 0) return 1;
    int x = expo(a, b/2);
    int y = mul(x, x);
    if(b%2) y = mul(y, a);
    return y;
}
int inv(int x)
{
    return expo(x, md-2);
}
int a[maxn];
int b[maxn];
int qu[maxn][2*maxn];
int f[maxn][2*maxn];
int sum[maxn][2*maxn];
int mem[maxn][2*maxn];
int n;
vi vec;
int g(int L, int R, int intv)
{
    //cout << L << ' ' << R << ' ' << intv << endl;
    int k = qu[R][intv]-qu[L-1][intv]-1;
    int sz = vec[intv+1]-vec[intv];
    if(mem[k][intv] != -1) return mem[k][intv];
    int res = 1;
    for(int i = sz; i<= sz+k; i++) res = mul(res, i);
    for(int i = 1; i<= k+1; i++) res = mul(res, inv(i));
    return mem[k][intv] = res;
}
int main()
{
    memset(mem, -1, sizeof mem);
    cin >> n;
    for(int i = 1; i<= n; i++)
    {
        cin >> a[i] >> b[i];
        b[i]++;
        vec.pb(a[i]); vec.pb(b[i]);
    }
    sort(vec.begin(), vec.end()); vec.resize(unique(vec.begin(), vec.end())-vec.begin());
    for(int i = 1; i<= n; i++)
    {
        a[i] = lower_bound(vec.begin(), vec.end(), a[i])-vec.begin();
        b[i] = lower_bound(vec.begin(), vec.end(), b[i])-vec.begin();
    }
    for(int i = 1; i<= n; i++)
    {
        for(int j = 0; j< (int) vec.size()-1; j++)
        {
            qu[i][j] = qu[i-1][j] + (a[i]<= j && j< b[i]);
        }
    }
    for(int L = 1; L<= n; L++)
    {
        for(int R = L+1; R<= n; R++)
        {
            for(int intv = 0; intv< (int) vec.size()-1; intv++) g(L, R, intv);
        }
    }
    for(int j = 0; j< (int) vec.size()-1; j++) sum[0][j] = 1;
    for(int i = 1; i<= n; i++)
    {
        for(int j = 0; j< (int) vec.size()-1; j++)
        {
            if(a[i]<= j && j <b[i])
            {
                for(int a = 0; a< i ; a++)
                {
                    int sm;
                    if(j == 0 && a == 0) sm = 1;
                    else if(j == 0) sm = 0;
                    else sm = sum[a][j-1];
                    //cout << sm << endl;
                    add(f[i][j], mul(sm, g(a+1, i, j)));
                }
            }
            //printf("f[%d][%d] = %d\n", i, j, f[i][j]);
            sum[i][j] = j?sum[i][j-1]:0;
            add(sum[i][j], f[i][j]);
        }
    }
    int res = 0;
    for(int i = 1; i<= n; i++)
    {
        for(int j = 0; j< (int) vec.size()-1; j++)
        {
            add(res, f[i][j]);
        }
    }
    cout << res << endl;
}

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	699 ms	7952 KB	Output is correct
2	Correct	705 ms	8040 KB	Output is correct
3	Correct	708 ms	8096 KB	Output is correct
4	Correct	723 ms	8276 KB	Output is correct
5	Correct	713 ms	8276 KB	Output is correct
6	Correct	705 ms	8524 KB	Output is correct
7	Correct	733 ms	8524 KB	Output is correct
8	Correct	708 ms	8524 KB	Output is correct
9	Correct	705 ms	8524 KB	Output is correct
10	Correct	712 ms	8524 KB	Output is correct
11	Correct	706 ms	8524 KB	Output is correct
12	Correct	707 ms	8536 KB	Output is correct
13	Correct	725 ms	8548 KB	Output is correct
14	Correct	812 ms	8548 KB	Output is correct
15	Correct	737 ms	8548 KB	Output is correct
16	Correct	138 ms	8548 KB	Output is correct
17	Correct	148 ms	8548 KB	Output is correct
18	Correct	145 ms	8548 KB	Output is correct
19	Correct	146 ms	8548 KB	Output is correct
20	Correct	143 ms	8548 KB	Output is correct

Subtask #2
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	699 ms	7952 KB	Output is correct
2	Correct	705 ms	8040 KB	Output is correct
3	Correct	708 ms	8096 KB	Output is correct
4	Correct	723 ms	8276 KB	Output is correct
5	Correct	713 ms	8276 KB	Output is correct
6	Correct	705 ms	8524 KB	Output is correct
7	Correct	733 ms	8524 KB	Output is correct
8	Correct	708 ms	8524 KB	Output is correct
9	Correct	705 ms	8524 KB	Output is correct
10	Correct	712 ms	8524 KB	Output is correct
11	Correct	706 ms	8524 KB	Output is correct
12	Correct	707 ms	8536 KB	Output is correct
13	Correct	725 ms	8548 KB	Output is correct
14	Correct	812 ms	8548 KB	Output is correct
15	Correct	737 ms	8548 KB	Output is correct
16	Correct	138 ms	8548 KB	Output is correct
17	Correct	148 ms	8548 KB	Output is correct
18	Correct	145 ms	8548 KB	Output is correct
19	Correct	146 ms	8548 KB	Output is correct
20	Correct	143 ms	8548 KB	Output is correct
21	Execution timed out	2063 ms	8548 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	63 ms	8548 KB	Output is correct
2	Correct	47 ms	8548 KB	Output is correct
3	Correct	61 ms	8548 KB	Output is correct
4	Correct	64 ms	8548 KB	Output is correct
5	Correct	71 ms	8548 KB	Output is correct
6	Correct	135 ms	8548 KB	Output is correct
7	Correct	137 ms	8548 KB	Output is correct
8	Correct	135 ms	8548 KB	Output is correct
9	Correct	135 ms	8548 KB	Output is correct
10	Correct	138 ms	8548 KB	Output is correct
11	Correct	69 ms	8548 KB	Output is correct
12	Correct	50 ms	8548 KB	Output is correct
13	Correct	62 ms	8548 KB	Output is correct
14	Correct	59 ms	8548 KB	Output is correct
15	Correct	70 ms	8548 KB	Output is correct
16	Correct	44 ms	8548 KB	Output is correct
17	Correct	36 ms	8548 KB	Output is correct
18	Correct	40 ms	8548 KB	Output is correct
19	Correct	36 ms	8548 KB	Output is correct
20	Correct	43 ms	8548 KB	Output is correct

Subtask #4
0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	699 ms	7952 KB	Output is correct
2	Correct	705 ms	8040 KB	Output is correct
3	Correct	708 ms	8096 KB	Output is correct
4	Correct	723 ms	8276 KB	Output is correct
5	Correct	713 ms	8276 KB	Output is correct
6	Correct	705 ms	8524 KB	Output is correct
7	Correct	733 ms	8524 KB	Output is correct
8	Correct	708 ms	8524 KB	Output is correct
9	Correct	705 ms	8524 KB	Output is correct
10	Correct	712 ms	8524 KB	Output is correct
11	Correct	706 ms	8524 KB	Output is correct
12	Correct	707 ms	8536 KB	Output is correct
13	Correct	725 ms	8548 KB	Output is correct
14	Correct	812 ms	8548 KB	Output is correct
15	Correct	737 ms	8548 KB	Output is correct
16	Correct	138 ms	8548 KB	Output is correct
17	Correct	148 ms	8548 KB	Output is correct
18	Correct	145 ms	8548 KB	Output is correct
19	Correct	146 ms	8548 KB	Output is correct
20	Correct	143 ms	8548 KB	Output is correct
21	Execution timed out	2063 ms	8548 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

답안 #47153

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