oj.uz

Submission #967191

# Submission time Handle Problem Language Result Execution time Memory
967191 2024-04-21T13:24:46 Z Roman70 trapezoid (balkan11_trapezoid) C++17
23 / 100
 500 ms 3664 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];
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++){
         for(int j = i+1;j<n;j++){
            if(a[i].b < a[j].a && a[i].d < a[j].c && dp[j] == ans-1) ans2 = (ans2 + 1) % mod;
        }
    }
    cout<<ans<<" "<<ans2;
    return 0;
}

Subtask #1
23.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Partially correct 0 ms 348 KB Partially correct
3 Partially correct 1 ms 348 KB Partially correct
4 Partially correct 2 ms 348 KB Partially correct
5 Partially correct 7 ms 508 KB Partially correct
6 Partially correct 14 ms 348 KB Partially correct
7 Partially correct 19 ms 348 KB Partially correct
8 Partially correct 29 ms 600 KB Partially correct
9 Partially correct 160 ms 768 KB Partially correct
10 Partially correct 400 ms 1112 KB Partially correct
11 Execution timed out 827 ms 1488 KB Time limit exceeded
12 Execution timed out 1070 ms 2132 KB Time limit exceeded
13 Execution timed out 1077 ms 2316 KB Time limit exceeded
14 Execution timed out 1049 ms 2932 KB Time limit exceeded
15 Execution timed out 1079 ms 2900 KB Time limit exceeded
16 Execution timed out 1061 ms 3228 KB Time limit exceeded
17 Execution timed out 1045 ms 3152 KB Time limit exceeded
18 Execution timed out 1045 ms 3412 KB Time limit exceeded
19 Execution timed out 1034 ms 3560 KB Time limit exceeded
20 Execution timed out 1043 ms 3664 KB Time limit exceeded