Submission #26194

#	Time	Username	Problem	Language	Result	Execution time	Memory
26194		Extazy	Boat (APIO16_boat)	C++14	9 / 100	2000 ms	7992 KiB

boat

#include <bits/stdc++.h>

using namespace std;

const int N = 517;
const int MOD = (1e9) + 7;

int n,a[N],b[N];
map < int, int > state[N];

int recurse(int pos, int last) {
    if(pos>n) {
        return ((last!=0) ? 1 : 0);
    }
    if(state[pos].find(last)!=state[pos].end()) {
        return state[pos][last];
    }
    long long ans=recurse(pos+1,last),i;
    for(i=max(last+1,a[pos]);i<=b[pos];i++) {
        ans+=recurse(pos+1,i);
    }
    ans%=MOD;
    state[pos][last]=ans;
    return ans;
}

int main() {
    int i;
    
    scanf("%d", &n);
    for(i=1;i<=n;i++) {
        scanf("%d %d", &a[i], &b[i]);
    }
    printf("%d\n", recurse(1,0));

    return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:30:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
boat.cpp:32:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a[i], &b[i]);
                                     ^

• Subtask 1: 9 / 9
• Subtask 2: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42