답안 #553696

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
553696	2022-04-26T16:05:12 Z	ala2	Boat (APIO16_boat)	C++14	9 / 100	2000 ms	524288 KB

boat

#include <bits/stdc++.h>
#define int long long
#define F first
#define S second
#define pb push_back
#define B begin()
#define E end()

using namespace std;
int n;
int a[1001000];
int b[1000100];
map<pair<pair<int,int>,int>,int>dp;
map<pair<pair<int,int>,int>,int>go;
const int mod=1e9+7;
//dp[ { {i,last},pl } ]
int f(int i,int last,int pl)
{
    if(go[ { {i,last},pl } ]!=0)
        return dp[ { {i,last},pl } ]%mod;
    if(i==n+1)
        return 1;
    int g=f(i+1,last,pl);
    for(int j=a[i];j<=b[i];j++)
    if(j>a[last]+pl)
        g+=f(i+1,i,j-a[i]);
    //cout<<"        "<<i<<"   "<<last<<"   "<<pl<<endl;
    go[ { {i,last},pl } ]=1;
    return dp[ { {i,last},pl } ]=g%mod;
}
signed main()
{
    //memset(dp,-1,sizeof dp);
    cin>>n;
    for(int i=1;i<=n;i++){
        //a[i]=n-i;
        cin>>a[i]>>b[i];
    }
        cout<<f(1,0,0)-1<<endl;

}

Subtask #1

9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	162 ms	19908 KB	Output is correct
2	Correct	145 ms	19976 KB	Output is correct
3	Correct	181 ms	20068 KB	Output is correct
4	Correct	203 ms	19964 KB	Output is correct
5	Correct	142 ms	19908 KB	Output is correct
6	Correct	162 ms	19996 KB	Output is correct
7	Correct	185 ms	20004 KB	Output is correct
8	Correct	159 ms	20024 KB	Output is correct
9	Correct	153 ms	19908 KB	Output is correct
10	Correct	177 ms	20072 KB	Output is correct
11	Correct	204 ms	19992 KB	Output is correct
12	Correct	165 ms	19924 KB	Output is correct
13	Correct	158 ms	20024 KB	Output is correct
14	Correct	205 ms	19964 KB	Output is correct
15	Correct	171 ms	19916 KB	Output is correct
16	Correct	143 ms	20024 KB	Output is correct
17	Correct	158 ms	20020 KB	Output is correct
18	Correct	165 ms	19916 KB	Output is correct
19	Correct	143 ms	19952 KB	Output is correct
20	Correct	140 ms	19976 KB	Output is correct

Subtask #2

0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	162 ms	19908 KB	Output is correct
2	Correct	145 ms	19976 KB	Output is correct
3	Correct	181 ms	20068 KB	Output is correct
4	Correct	203 ms	19964 KB	Output is correct
5	Correct	142 ms	19908 KB	Output is correct
6	Correct	162 ms	19996 KB	Output is correct
7	Correct	185 ms	20004 KB	Output is correct
8	Correct	159 ms	20024 KB	Output is correct
9	Correct	153 ms	19908 KB	Output is correct
10	Correct	177 ms	20072 KB	Output is correct
11	Correct	204 ms	19992 KB	Output is correct
12	Correct	165 ms	19924 KB	Output is correct
13	Correct	158 ms	20024 KB	Output is correct
14	Correct	205 ms	19964 KB	Output is correct
15	Correct	171 ms	19916 KB	Output is correct
16	Correct	143 ms	20024 KB	Output is correct
17	Correct	158 ms	20020 KB	Output is correct
18	Correct	165 ms	19916 KB	Output is correct
19	Correct	143 ms	19952 KB	Output is correct
20	Correct	140 ms	19976 KB	Output is correct
21	Execution timed out	2067 ms	4528 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

Subtask #3

0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	1972 ms	524288 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	162 ms	19908 KB	Output is correct
2	Correct	145 ms	19976 KB	Output is correct
3	Correct	181 ms	20068 KB	Output is correct
4	Correct	203 ms	19964 KB	Output is correct
5	Correct	142 ms	19908 KB	Output is correct
6	Correct	162 ms	19996 KB	Output is correct
7	Correct	185 ms	20004 KB	Output is correct
8	Correct	159 ms	20024 KB	Output is correct
9	Correct	153 ms	19908 KB	Output is correct
10	Correct	177 ms	20072 KB	Output is correct
11	Correct	204 ms	19992 KB	Output is correct
12	Correct	165 ms	19924 KB	Output is correct
13	Correct	158 ms	20024 KB	Output is correct
14	Correct	205 ms	19964 KB	Output is correct
15	Correct	171 ms	19916 KB	Output is correct
16	Correct	143 ms	20024 KB	Output is correct
17	Correct	158 ms	20020 KB	Output is correct
18	Correct	165 ms	19916 KB	Output is correct
19	Correct	143 ms	19952 KB	Output is correct
20	Correct	140 ms	19976 KB	Output is correct
21	Execution timed out	2067 ms	4528 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-