oj.uz

답안 #31933

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
31933 2017-09-16T09:09:07 Z Extazy 사다리꼴 (balkan11_trapezoid) C++14
45 / 100
 500 ms 22880 KB 
#include <bits/stdc++.h>
#define endl '\n'

#define left aklhgjqghkqkj
#define right ajklvhajkvhajk
#define prev aioghajga
#define next ioyhjhfajasj
#define y0 iuadoghasdgj
#define y1 taklahgjkla
#define remainder pogjuakllhga
#define pow pajklgaklha
#define pow10 iopuioadjlgkah
#define div aljghajkghak
#define distance gkuftgjasgfjh
#define uppercase ifyhasjkhakjfas
#define tm aogqjgklqjgqklgjqlkq

//#define floor hjakjhaja
//#define time ashjlahjka
//#define double_t double

using namespace std;

const int N = 1<<17;
const int MOD = 30013;

struct trapezoid {
    pair < int, int > ac, bd;
    bool operator <(const trapezoid &a) const {
        return bd<a.bd;
    }
};

int n,sz,p[N*4];
map < int, int > code;
int all;
int ans;
trapezoid a[N];
int anscnt;
int cnt[N],dp[N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int i,j,x,y,z,w;

    scanf("%d", &n);
    for(i=1;i<=n;i++) {
        scanf("%d %d %d %d", &x, &y, &z, &w);
        a[i].ac=make_pair(x,z);
        a[i].bd=make_pair(y,w);
        p[++sz]=a[i].ac.first;
        p[++sz]=a[i].ac.second;
        p[++sz]=a[i].bd.first;
        p[++sz]=a[i].bd.second;
    }

    sort(p+1,p+1+sz);
    code[p[1]]=1;
    for(i=2;i<=sz;i++) if(p[i]!=p[i-1]) {
        code[p[i]]=code[p[i-1]]+1;
    }
    all=code[p[sz]];

    for(i=1;i<=n;i++) {
        a[i].ac=make_pair(code[a[i].ac.first],code[a[i].ac.second]);
        a[i].bd=make_pair(code[a[i].bd.first],code[a[i].bd.second]);
    }

    sort(a+1,a+1+n);
    for(i=1;i<=n;i++) {
        int curr=1;
        for(j=i-1;j>=1;j--) {
            if(a[j].bd.first<a[i].ac.first && a[j].bd.second<a[i].ac.second) {
                curr=max(curr,1+dp[j]);
            }
        }
        dp[i]=curr;
        ans=max(ans,curr);
        if(curr==1) {
            cnt[i]=1;
        }
        else {
            for(j=i-1;j>=1;j--) {
                if(a[j].bd.first<a[i].ac.first && a[j].bd.second<a[i].ac.second) {
                    if(dp[j]+1==dp[i]) {
                        cnt[i]=(cnt[i]+cnt[j])%MOD;
                    }
                }
            }
        }
    }

    for(i=1;i<=n;i++) {
        if(dp[i]==ans) {
            anscnt=(anscnt+cnt[i])%MOD;
        }
    }
    
    printf("%d %d\n", ans, anscnt);

    return 0;
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:47:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
trapezoid.cpp:49:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d", &x, &y, &z, &w);
                                             ^

Subtask #1
45.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 7304 KB Output is correct
2 Correct 0 ms 7304 KB Output is correct
3 Correct 0 ms 7304 KB Output is correct
4 Correct 3 ms 7436 KB Output is correct
5 Correct 9 ms 7568 KB Output is correct
6 Correct 23 ms 7832 KB Output is correct
7 Correct 29 ms 7700 KB Output is correct
8 Correct 49 ms 7964 KB Output is correct
9 Correct 249 ms 9020 KB Output is correct
10 Execution timed out 500 ms 9152 KB Execution timed out
11 Execution timed out 500 ms 11528 KB Execution timed out
12 Execution timed out 500 ms 16148 KB Execution timed out
13 Execution timed out 500 ms 17468 KB Execution timed out
14 Execution timed out 500 ms 19844 KB Execution timed out
15 Execution timed out 500 ms 18260 KB Execution timed out
16 Execution timed out 500 ms 18920 KB Execution timed out
17 Execution timed out 500 ms 21428 KB Execution timed out
18 Execution timed out 500 ms 15752 KB Execution timed out
19 Execution timed out 500 ms 22616 KB Execution timed out
20 Execution timed out 500 ms 22880 KB Execution timed out