oj.uz

Submission #377654

# Submission time Handle Problem Language Result Execution time Memory
377654 2021-03-14T15:30:27 Z ntabc05101 trapezoid (balkan11_trapezoid) C++14
50 / 100
 500 ms 2668 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[i].s>=mod) {
                                                dp[i].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
50.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 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 7 ms 364 KB Output is correct
6 Correct 14 ms 364 KB Output is correct
7 Correct 18 ms 364 KB Output is correct
8 Correct 19 ms 492 KB Output is correct
9 Correct 119 ms 620 KB Output is correct
10 Correct 414 ms 748 KB Output is correct
11 Execution timed out 810 ms 876 KB Time limit exceeded
12 Execution timed out 1046 ms 1772 KB Time limit exceeded
13 Execution timed out 1094 ms 1772 KB Time limit exceeded
14 Execution timed out 1097 ms 1900 KB Time limit exceeded
15 Execution timed out 1097 ms 2028 KB Time limit exceeded
16 Execution timed out 1041 ms 2284 KB Time limit exceeded
17 Execution timed out 1091 ms 2284 KB Time limit exceeded
18 Execution timed out 1082 ms 2412 KB Time limit exceeded
19 Execution timed out 1088 ms 2540 KB Time limit exceeded
20 Execution timed out 1088 ms 2668 KB Time limit exceeded