답안 #282531

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
282531	2020-08-24T14:15:54 Z	AaronNaidu	Boat (APIO16_boat)	C++14	0 / 100	5 ms	2432 KB

boat

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

ll mod = 1000000007; 
int n;
ll x;
vector<ll> v;
vector<pair<ll, int> > ycoords;
int indexes[501];

ll dp[501][501];

ll getDP(int a, int b) {
    if (a == -1)
    {
        return 1;
    }
    if (dp[a][b] > 0)
    {
        return dp[a][b];
    }
    
    ll ans = 0;
    if (ycoords[b].first >= v[a])
    {
        ans += getDP(a-1, indexes[a]);
        ans %= mod;
    }
    ans += getDP(a-1, b);
    ans %= mod;
    dp[a][b] = ans;
    return ans;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> x >> x;
        v.push_back(x);
        ycoords.push_back({x, i});
    }
    sort(ycoords.begin(), ycoords.end());
    for (int i = 0; i < n; i++)
    {
        indexes[ycoords[i].second] = i;
    }
    ll ans = getDP(n-1, n-1) - 1;
    if (ans < 0)
    {
        ans += mod;
    }
    
    ans %= mod;
    cout << ans << "\n";
}

Subtask #1

0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	2432 KB	Output is correct
2	Correct	5 ms	2304 KB	Output is correct
3	Correct	4 ms	2304 KB	Output is correct
4	Correct	4 ms	2304 KB	Output is correct
5	Correct	4 ms	2304 KB	Output is correct
6	Correct	4 ms	2304 KB	Output is correct
7	Correct	4 ms	2304 KB	Output is correct
8	Correct	4 ms	2304 KB	Output is correct
9	Correct	5 ms	2304 KB	Output is correct
10	Correct	4 ms	2280 KB	Output is correct
11	Correct	5 ms	2304 KB	Output is correct
12	Correct	4 ms	2304 KB	Output is correct
13	Correct	4 ms	2304 KB	Output is correct
14	Correct	4 ms	2304 KB	Output is correct
15	Correct	4 ms	2304 KB	Output is correct
16	Incorrect	5 ms	2304 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #2

0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	2432 KB	Output is correct
2	Correct	5 ms	2304 KB	Output is correct
3	Correct	4 ms	2304 KB	Output is correct
4	Correct	4 ms	2304 KB	Output is correct
5	Correct	4 ms	2304 KB	Output is correct
6	Correct	4 ms	2304 KB	Output is correct
7	Correct	4 ms	2304 KB	Output is correct
8	Correct	4 ms	2304 KB	Output is correct
9	Correct	5 ms	2304 KB	Output is correct
10	Correct	4 ms	2280 KB	Output is correct
11	Correct	5 ms	2304 KB	Output is correct
12	Correct	4 ms	2304 KB	Output is correct
13	Correct	4 ms	2304 KB	Output is correct
14	Correct	4 ms	2304 KB	Output is correct
15	Correct	4 ms	2304 KB	Output is correct
16	Incorrect	5 ms	2304 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #3

0 / 27.0

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

Subtask #4

0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	2432 KB	Output is correct
2	Correct	5 ms	2304 KB	Output is correct
3	Correct	4 ms	2304 KB	Output is correct
4	Correct	4 ms	2304 KB	Output is correct
5	Correct	4 ms	2304 KB	Output is correct
6	Correct	4 ms	2304 KB	Output is correct
7	Correct	4 ms	2304 KB	Output is correct
8	Correct	4 ms	2304 KB	Output is correct
9	Correct	5 ms	2304 KB	Output is correct
10	Correct	4 ms	2280 KB	Output is correct
11	Correct	5 ms	2304 KB	Output is correct
12	Correct	4 ms	2304 KB	Output is correct
13	Correct	4 ms	2304 KB	Output is correct
14	Correct	4 ms	2304 KB	Output is correct
15	Correct	4 ms	2304 KB	Output is correct
16	Incorrect	5 ms	2304 KB	Output isn't correct
17	Halted	0 ms	0 KB	-