oj.uz

Submission #110827

# Submission time Handle Problem Language Result Execution time Memory
110827 2019-05-12T10:33:33 Z baneling100 Boat (APIO16_boat) C++11
0 / 100
 293 ms 2040 KB 
/* 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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 293 ms 2040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 293 ms 2040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 81 ms 784 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Incorrect 293 ms 2040 KB Output isn't correct
2 Halted 0 ms 0 KB -