oj.uz

Submission #967188

# Submission time Handle Problem Language Result Execution time Memory
967188 2024-04-21T13:22:42 Z Roman70 trapezoid (balkan11_trapezoid) C++17
23 / 100
 500 ms 6548 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;
ll 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);
    ll 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]);
    }
    int 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 348 KB Output is correct
2 Partially correct 1 ms 348 KB Partially correct
3 Partially correct 2 ms 348 KB Partially correct
4 Partially correct 3 ms 344 KB Partially correct
5 Partially correct 7 ms 544 KB Partially correct
6 Partially correct 13 ms 856 KB Partially correct
7 Partially correct 19 ms 616 KB Partially correct
8 Partially correct 29 ms 600 KB Partially correct
9 Partially correct 153 ms 1032 KB Partially correct
10 Partially correct 414 ms 1876 KB Partially correct
11 Execution timed out 797 ms 2072 KB Time limit exceeded
12 Execution timed out 1055 ms 3644 KB Time limit exceeded
13 Execution timed out 1022 ms 4292 KB Time limit exceeded
14 Execution timed out 1052 ms 4924 KB Time limit exceeded
15 Execution timed out 1002 ms 5516 KB Time limit exceeded
16 Execution timed out 1045 ms 5596 KB Time limit exceeded
17 Execution timed out 1054 ms 5680 KB Time limit exceeded
18 Execution timed out 1068 ms 6308 KB Time limit exceeded
19 Execution timed out 1037 ms 6300 KB Time limit exceeded
20 Execution timed out 1069 ms 6548 KB Time limit exceeded