oj.uz

Submission #967192

# Submission time Handle Problem Language Result Execution time Memory
967192 2024-04-21T13:32:24 Z Roman70 trapezoid (balkan11_trapezoid) C++17
50 / 100
 500 ms 3816 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct trapezoid{
    ll a,b,c,d;
};
bool cmp(trapezoid &a, trapezoid &b){
    return a.a < b.a;
}
const int sz = 1e5+1;
int dp[sz];
int dp2[sz];
const int mod = 30013;
int main()
{
    int n;
    cin >> n;
    trapezoid a[n];
    for(int i = 0 ;i<n;i++){
        cin >> a[i].a >> a[i].b >> a[i].c >> a[i].d;
    }
    
    sort(a,a+n,cmp);
    int ans = 0;
    map<int,int>cnt;
    for(int i = n-1;i>=0;i--){
        dp[i] = 1;
        for(int j = i;j<n;j++){
            if(a[i].b < a[j].a && a[i].d < a[j].c) dp[i] = max(dp[i],dp[j]+1);
        }
        ans = max(ans,dp[i]);
    }
    ll ans2 = 0;
    for(int i =0;i<n;i++) if(dp[i] == 1) dp2[i] = 1;

    for(int i = n-1; i >= 0; i--){
         for(int j = i+1;j<n;j++){
            if(a[i].b < a[j].a && a[i].d < a[j].c && dp[j] == dp[i]-1) dp2[i] = (dp2[i] + dp2[j]) % mod;
        }
        if(dp[i] == ans) ans2 = (ans2 + dp2[i]) % mod;
    }

   
    cout<<ans<<" "<<ans2;
    return 0;
}

Subtask #1
50.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 7 ms 344 KB Output is correct
6 Correct 14 ms 348 KB Output is correct
7 Correct 18 ms 604 KB Output is correct
8 Correct 28 ms 600 KB Output is correct
9 Correct 151 ms 768 KB Output is correct
10 Correct 391 ms 1172 KB Output is correct
11 Execution timed out 881 ms 1624 KB Time limit exceeded
12 Execution timed out 1056 ms 2132 KB Time limit exceeded
13 Execution timed out 1066 ms 2648 KB Time limit exceeded
14 Execution timed out 1047 ms 2960 KB Time limit exceeded
15 Execution timed out 1067 ms 3076 KB Time limit exceeded
16 Execution timed out 1020 ms 3060 KB Time limit exceeded
17 Execution timed out 1061 ms 3096 KB Time limit exceeded
18 Execution timed out 1016 ms 3352 KB Time limit exceeded
19 Execution timed out 1029 ms 3692 KB Time limit exceeded
20 Execution timed out 1065 ms 3816 KB Time limit exceeded