Submission #110827

#	Time	Username	Problem	Language	Result	Execution time	Memory
110827		baneling100	Boat (APIO16_boat)	C++11	0 / 100	293 ms	2040 KiB

boat

/* without consideration of time complexity */

#include <cstdio>
#include <algorithm>
#define MOD 1000000007

using namespace std;

pair <int, pair <int, int> > P[1001];
int N, A[501], B[501]; // left and right location of C
int M, C[1001]; // have pressed coordination
int D0[501], D1[501][1001], Ans;

int main() {
    
    int x, y;
    
    scanf("%d ", &N);
    for(int i = 1; i <= N; i++) {
        scanf("%d %d ", &x, &y);
        x--;
        P[2 * i - 1] = make_pair(x, make_pair(i, -1));
        P[2 * i    ] = make_pair(y, make_pair(i,  1));
    }
    
    sort(P + 1, P + 2 * N + 1);
    
    P[0].first = -1;
    
    for(int i = 1; i <= 2 * N; i++) {
        if(P[i].first != P[i - 1].first)
            C[++M] = P[i].first;
        
        if(P[i].second.second == -1) // left
            A[P[i].second.first] = M;
        else // right
            B[P[i].second.first] = M;
    }
    
    D0[0] = 1;
    
    for(int i = 1; i <= N; i++) {
        D0[i] = D0[i - 1];
        for(int j = 2; j <= M; j++) {
            D0[i] += D1[i - 1][j];
            D0[i] %= MOD;
        }
        
        for(int j = A[i] + 1; j <= B[i]; j++) {
            D1[i][j] = C[j] - C[j - 1]; // nothing
            long long sum = 0;
            for(int k = 1; k < i; k++)
                for(int l = 2; l <= A[i]; l++) {
                    sum += D1[k][l];
                    sum %= MOD;
                }
                
            sum *= C[j] - C[j - 1];
            sum %= MOD;
            
            D1[i][j] += sum;
            D1[i][j] %= MOD;
        }
    }
    
    Ans = D0[N];
    for(int i = 2; i <= M; i++) {
        Ans += D1[N][i];
        Ans %= MOD;
    }
    
    printf("%d\n", Ans);
    
    return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d ", &N);
     ~~~~~^~~~~~~~~~~
boat.cpp:20:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d ", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~~~

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