oj.uz

Submission #377653

# Submission time Handle Problem Language Result Execution time Memory
377653 2021-03-14T15:27:42 Z ntabc05101 trapezoid (balkan11_trapezoid) C++14
26 / 100
 500 ms 2924 KB 
#ifndef LOCAL
#define NDEBUG 1
#endif // LOCAL
#include<bits/stdc++.h>

#define taskname ""

#define f first
#define s second

const int inf=1e9+9;
const int mod=30013;

int main() {
        if (fopen(taskname".inp", "r")) {
                freopen(taskname".inp", "r", stdin);
                freopen(taskname".out", "w", stdout);
        }
        else if (fopen(taskname".in", "r")) {
                freopen(taskname".in", "r", stdin);
                freopen(taskname".out", "w", stdout);
        }

        std::ios_base::sync_with_stdio(0); std::cin.tie(0);

        int n; std::cin>>n;
        std::pair< std::pair<int, int>, std::pair<int, int> > a[n+5];
        a[0].f.f=a[0].f.s=a[0].s.f=a[0].s.s=0;
        a[n+1].f.f=a[n+1].f.s=a[n+1].s.f=a[n+1].s.s=inf;
        for (int i=1; i<=n; ++i) {
                std::cin>>a[i].s.s>>a[i].f.s>>a[i].s.f>>a[i].f.f;
        }

        std::sort(a+1, a+n+1);

        std::pair<int, int> dp[n+5];
        memset(dp, 0, sizeof(dp));
        dp[0].s=1;

        for (int i=1; i<=n+1; ++i) {
                for (int j=0; j<i; ++j) {
                        if (a[i].s.s>=a[j].f.s and a[i].s.f>=a[j].f.f) {
                                if (dp[i].f<dp[j].f+1) {
                                        dp[i].f=dp[j].f+1;
                                        dp[i].s=dp[j].s;
                                }
                                else if (dp[i].f==dp[j].f+1) {
                                        dp[i].s+=dp[j].s;
                                        if (dp[j].s>=mod) {
                                                dp[j].s-=mod;
                                        }
                                }
                        }
                }
        }

        std::cout<<dp[n+1].f-1<<" "<<dp[n+1].s<<"\n";

        return 0;
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   16 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   17 |                 freopen(taskname".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:20:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   20 |                 freopen(taskname".in", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:21:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   21 |                 freopen(taskname".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
26.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Partially correct 1 ms 364 KB Partially correct
4 Partially correct 2 ms 364 KB Partially correct
5 Partially correct 7 ms 364 KB Partially correct
6 Partially correct 14 ms 364 KB Partially correct
7 Partially correct 22 ms 364 KB Partially correct
8 Partially correct 19 ms 492 KB Partially correct
9 Partially correct 119 ms 620 KB Partially correct
10 Partially correct 441 ms 876 KB Partially correct
11 Execution timed out 814 ms 1004 KB Time limit exceeded
12 Execution timed out 1050 ms 1516 KB Time limit exceeded
13 Execution timed out 1044 ms 1772 KB Time limit exceeded
14 Execution timed out 1050 ms 2028 KB Time limit exceeded
15 Execution timed out 1060 ms 2028 KB Time limit exceeded
16 Execution timed out 1091 ms 2156 KB Time limit exceeded
17 Execution timed out 1045 ms 2284 KB Time limit exceeded
18 Execution timed out 1057 ms 2412 KB Time limit exceeded
19 Execution timed out 1049 ms 2540 KB Time limit exceeded
20 Execution timed out 1066 ms 2924 KB Time limit exceeded