Submission #377653

#	Time	Username	Problem	Language	Result	Execution time	Memory
377653		ntabc05101	trapezoid (balkan11_trapezoid)	C++14	26 / 100	1091 ms	2924 KiB

trapezoid

#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 (stderr)

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 / 100