oj.uz

Submission #12031

# Submission time Handle Problem Language Result Execution time Memory
12031 2014-12-19T03:41:46 Z gs14004 trapezoid (balkan11_trapezoid) C++
35 / 100
 500 ms 6252 KB 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int n;
int a[100005], b[100005], c[100005], d[100005];
vector<int> vu, vd;
int dp[100005], cnt[100005];

int main(){
    scanf("%d",&n);
    for (int i=0; i<n; i++) {
        scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);
        vu.push_back(a[i]);
        vu.push_back(b[i]);
        vd.push_back(c[i]);
        vd.push_back(d[i]);
    }
    sort(vu.begin(),vu.end());
    sort(vd.begin(),vd.end());
    for (int i=0; i<n; i++) {
        a[i] = (int)(lower_bound(vu.begin(),vu.end(),a[i]) - vu.begin());
        b[i] = (int)(lower_bound(vu.begin(),vu.end(),b[i]) - vu.begin());
        c[i] = (int)(lower_bound(vd.begin(),vd.end(),c[i]) - vd.begin());
        d[i] = (int)(lower_bound(vd.begin(),vd.end(),d[i]) - vd.begin());
    }
    for (int i=0; i<n; i++) {
        dp[i] = 1;
        for (int j=0; j<n; j++) {
            if(b[j] < a[i] && d[j] < c[i]){
                dp[i] = max(dp[i],dp[j]+1);
            }
        }
        for (int j=0; j<n; j++) {
            if(dp[j] + 1 == dp[i] && b[j] < a[i] && d[j] < c[i]){
                cnt[i] += cnt[j];
                cnt[i] %= 30013;
            }
        }
        if(dp[i] == 1) cnt[i] = 1;
    }
    int mcnt = *max_element(dp,dp+n);
    int rcnt = 0;
    for (int i=0; i<n; i++) {
        if(dp[i] == mcnt){
            rcnt += cnt[i];
            rcnt %= 30013;
        }
    }
    printf("%d %d",mcnt,rcnt);
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:12:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
trapezoid.cpp:14:53: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);
                                                     ^

Subtask #1
35.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3520 KB Output is correct
2 Correct 0 ms 3520 KB Output is correct
3 Correct 0 ms 3520 KB Output is correct
4 Incorrect 3 ms 3520 KB Output isn't correct
5 Correct 9 ms 3520 KB Output is correct
6 Correct 19 ms 3680 KB Output is correct
7 Incorrect 36 ms 3680 KB Output isn't correct
8 Correct 76 ms 3680 KB Output is correct
9 Correct 249 ms 3812 KB Output is correct
10 Execution timed out 500 ms 4200 KB Execution timed out
11 Execution timed out 500 ms 4200 KB Execution timed out
12 Execution timed out 500 ms 4972 KB Execution timed out
13 Execution timed out 500 ms 4972 KB Execution timed out
14 Execution timed out 500 ms 6252 KB Execution timed out
15 Execution timed out 500 ms 6252 KB Execution timed out
16 Execution timed out 500 ms 6252 KB Execution timed out
17 Execution timed out 500 ms 6252 KB Execution timed out
18 Execution timed out 500 ms 6252 KB Execution timed out
19 Execution timed out 500 ms 6252 KB Execution timed out
20 Execution timed out 500 ms 6252 KB Execution timed out