답안 #32227

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
32227	2017-10-05T02:03:50 Z	dqhungdl	Boat (APIO16_boat)	C++14	9 / 100	2000 ms	48516 KB

boat

#include <bits/stdc++.h>
using namespace std;

const int mod=1e9+7;
int n,MAX=0,res=0,a[505],b[505],f[505];
map<int,int> tree;

void Sub1()
{
    for(int i=1;i<=n;i++)
    {
        f[i]=1;
        for(int j=1;j<i;j++)
            if(a[j]<a[i])
                f[i]=(f[i]+f[j])%mod;
        res=(res+f[i])%mod;
    }
    cout<<res;
}

void Update(int idx,int data)
{
    while(idx<=MAX)
    {
        tree[idx]=(tree[idx]+data)%mod;
        idx+=idx&-idx;
    }
}

int Query(int idx)
{
    int rs=0;
    while(idx>0)
    {
        rs=(rs+tree[idx])%mod;
        idx-=idx&-idx;
    }
    return rs;
}

void Sub2()
{
    for(int i=1;i<=n;i++)
        for(int j=b[i];j>=a[i];j--)
        {
            int tmp=Query(j-1)+1;
            Update(j,tmp);
            res=(res+tmp)%mod;
        }
    cout<<res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("BOAT.INP","r",stdin);
    cin>>n;
    int maxn=0;
    bool check=false;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i];
        if(a[i]!=b[i])
            check=true;
        maxn=max(maxn,b[i]-a[i]);
        MAX=max(MAX,b[i]);
    }
    if(check==false)
        Sub1();
    else
    if(maxn<=1e6)
        Sub2();
}

Subtask #1

9.0 / 9.0

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

Subtask #2

0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2184 KB	Output is correct
2	Correct	0 ms	2184 KB	Output is correct
3	Correct	0 ms	2184 KB	Output is correct
4	Correct	0 ms	2184 KB	Output is correct
5	Correct	0 ms	2184 KB	Output is correct
6	Correct	0 ms	2184 KB	Output is correct
7	Correct	0 ms	2184 KB	Output is correct
8	Correct	0 ms	2184 KB	Output is correct
9	Correct	0 ms	2184 KB	Output is correct
10	Correct	0 ms	2184 KB	Output is correct
11	Correct	0 ms	2184 KB	Output is correct
12	Correct	0 ms	2184 KB	Output is correct
13	Correct	0 ms	2184 KB	Output is correct
14	Correct	0 ms	2184 KB	Output is correct
15	Correct	0 ms	2184 KB	Output is correct
16	Correct	0 ms	2184 KB	Output is correct
17	Correct	0 ms	2184 KB	Output is correct
18	Correct	0 ms	2184 KB	Output is correct
19	Correct	0 ms	2184 KB	Output is correct
20	Correct	0 ms	2184 KB	Output is correct
21	Correct	1043 ms	2448 KB	Output is correct
22	Correct	1006 ms	2448 KB	Output is correct
23	Correct	909 ms	2448 KB	Output is correct
24	Correct	1049 ms	2448 KB	Output is correct
25	Correct	1012 ms	2448 KB	Output is correct
26	Correct	1069 ms	2316 KB	Output is correct
27	Correct	1053 ms	2316 KB	Output is correct
28	Correct	1073 ms	2316 KB	Output is correct
29	Correct	1076 ms	2316 KB	Output is correct
30	Execution timed out	2000 ms	48516 KB	Execution timed out
31	Halted	0 ms	0 KB	-

Subtask #3

0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	0 ms	2184 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2184 KB	Output is correct
2	Correct	0 ms	2184 KB	Output is correct
3	Correct	0 ms	2184 KB	Output is correct
4	Correct	0 ms	2184 KB	Output is correct
5	Correct	0 ms	2184 KB	Output is correct
6	Correct	0 ms	2184 KB	Output is correct
7	Correct	0 ms	2184 KB	Output is correct
8	Correct	0 ms	2184 KB	Output is correct
9	Correct	0 ms	2184 KB	Output is correct
10	Correct	0 ms	2184 KB	Output is correct
11	Correct	0 ms	2184 KB	Output is correct
12	Correct	0 ms	2184 KB	Output is correct
13	Correct	0 ms	2184 KB	Output is correct
14	Correct	0 ms	2184 KB	Output is correct
15	Correct	0 ms	2184 KB	Output is correct
16	Correct	0 ms	2184 KB	Output is correct
17	Correct	0 ms	2184 KB	Output is correct
18	Correct	0 ms	2184 KB	Output is correct
19	Correct	0 ms	2184 KB	Output is correct
20	Correct	0 ms	2184 KB	Output is correct
21	Correct	1043 ms	2448 KB	Output is correct
22	Correct	1006 ms	2448 KB	Output is correct
23	Correct	909 ms	2448 KB	Output is correct
24	Correct	1049 ms	2448 KB	Output is correct
25	Correct	1012 ms	2448 KB	Output is correct
26	Correct	1069 ms	2316 KB	Output is correct
27	Correct	1053 ms	2316 KB	Output is correct
28	Correct	1073 ms	2316 KB	Output is correct
29	Correct	1076 ms	2316 KB	Output is correct
30	Execution timed out	2000 ms	48516 KB	Execution timed out
31	Halted	0 ms	0 KB	-