oj.uz

Submission #1053629

# Submission time Handle Problem Language Result Execution time Memory
1053629 2024-08-11T14:40:45 Z MinhBoss trapezoid (balkan11_trapezoid) C++17
10 / 100
 20 ms 1160 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define se second
#define endl '\n'
#define pb push_back

struct TrapeZoid{
    ll uL, uR, dR, dL;
    TrapeZoid(ll _uL=0, ll _uR=0, ll _dL=0, ll _dR=0){
        uL = _uL;
        uR = _uR;
        dR = _dR;
        dL = _dL;
    }
};

const ll MAX = 5e3;
ll n;
TrapeZoid a[MAX];
pair<ll,ll> dp[MAX];

bool intersect(ll i, ll j){
    if(a[i].uL > a[j].uR || a[i].uR < a[j].uL){
        if(a[i].dL > a[j].dR || a[i].dR < a[j].dL) return false;
    }
    return true;
}

int main(){
    cin>>n;
    for(int i =1;i<=n;i++){
        ll x,y,z,d; cin>>x>>y>>z>>d;
        a[i] = TrapeZoid(x,y,z,d);
    }
    for(int i =1;i<=n;i++){
        dp[i] = {1,1};
        for(int j = i-1; j>=1; j--){
            if(!intersect(i,j)){
                if(dp[i].fi == dp[j].fi + 1) dp[i].se += dp[j].se;
                else if(dp[i].fi < dp[j].fi + 1){
                    dp[i] = {dp[j].fi+1, dp[j].se};
                }
            }
        }

    }
    ll res=0, mx=0;
    for(int i =1;i<=n;i++){
        mx = max(mx, dp[i].fi);
    }
    for(int i =1;i<=n;i++){
        if(dp[i].fi == mx) res += dp[i].se;
    }
    cout<<mx<<" "<<res;

}

Subtask #1
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Incorrect 1 ms 604 KB Expected int32, but "3401477743242181632" found
4 Incorrect 1 ms 616 KB Expected int32, but "6732990656645414912" found
5 Incorrect 3 ms 668 KB Expected int32, but "4556332380006373312" found
6 Incorrect 7 ms 600 KB Expected int32, but "5156819809940963328" found
7 Incorrect 10 ms 748 KB Expected int32, but "7780866494695440384" found
8 Incorrect 20 ms 604 KB Output isn't correct
9 Runtime error 3 ms 1116 KB Execution killed with signal 11
10 Runtime error 4 ms 1128 KB Execution killed with signal 11
11 Runtime error 3 ms 1116 KB Execution killed with signal 11
12 Runtime error 3 ms 1116 KB Execution killed with signal 11
13 Runtime error 3 ms 1068 KB Execution killed with signal 11
14 Runtime error 4 ms 1160 KB Execution killed with signal 11
15 Runtime error 3 ms 1116 KB Execution killed with signal 11
16 Runtime error 3 ms 1116 KB Execution killed with signal 11
17 Runtime error 3 ms 1116 KB Execution killed with signal 11
18 Runtime error 3 ms 1116 KB Execution killed with signal 11
19 Runtime error 3 ms 1116 KB Execution killed with signal 11
20 Runtime error 3 ms 1116 KB Execution killed with signal 11