Submission #1442064
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll> P; #define fi first #define se second #define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++) #define rep(i,n) repl(i,0,n) #define each(itr,v) for(auto itr:v) #define pb push_back #define all(x) (x).begin(),(x).end() #define dbg(x) cout<<#x"="<<x<<endl #define mmax(x,y) (x>y?x:y) #define mmin(x,y) (x<y?x:y) #define maxch(x,y) x=mmax(x,y) #define minch(x,y) x=mmin(x,y) #define uni(x) x.erase(unique(all(x)),x.end()) #define exist(x,y) (find(all(x),y)!=x.end()) #define bcnt __builtin_popcount #define INF INT_MAX/3 bool sorter(const P& a,const P& b){ if(a.fi==b.fi)return a.se>b.se; else return a.fi<b.fi; } int n; int dp[111111]; P ps[111111]; int main(){ cin.sync_with_stdio(false); cin>>n; rep(i,n){ int a,b; cin>>a>>b; ps[i]=P(a,b); } rep(i,111111)dp[i]=INF; sort(ps,ps+n,sorter); dp[0]=0; rep(i,n){ *lower_bound(dp,dp+111111,ps[i].se)=ps[i].se; } rep(i,111111){ if(dp[i]==INF){ cout<<i-1<<endl; break; } } return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - プレゼント |
User | yamad |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 1166 Byte |
Status | AC |
Exec Time | 33 ms |
Memory | 2304 KB |
Judge Result
Set Name | Sample | Subtask0 | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 30 / 30 | 70 / 70 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample0.txt, sample1.txt, sample2.txt, sample3.txt |
Subtask0 | subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, sample0.txt, sample1.txt, sample2.txt, sample3.txt |
All | sample0.txt, sample1.txt, sample2.txt, sample3.txt, subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_2.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample0.txt | AC | 1 ms | 640 KB |
sample1.txt | AC | 1 ms | 640 KB |
sample2.txt | AC | 1 ms | 640 KB |
sample3.txt | AC | 1 ms | 640 KB |
subtask0_0.txt | AC | 1 ms | 768 KB |
subtask0_1.txt | AC | 1 ms | 640 KB |
subtask0_10.txt | AC | 2 ms | 768 KB |
subtask0_11.txt | AC | 1 ms | 768 KB |
subtask0_12.txt | AC | 2 ms | 768 KB |
subtask0_13.txt | AC | 2 ms | 768 KB |
subtask0_14.txt | AC | 1 ms | 768 KB |
subtask0_2.txt | AC | 1 ms | 640 KB |
subtask0_3.txt | AC | 1 ms | 768 KB |
subtask0_4.txt | AC | 1 ms | 768 KB |
subtask0_5.txt | AC | 1 ms | 640 KB |
subtask0_6.txt | AC | 2 ms | 768 KB |
subtask0_7.txt | AC | 1 ms | 768 KB |
subtask0_8.txt | AC | 2 ms | 768 KB |
subtask0_9.txt | AC | 1 ms | 640 KB |
subtask1_0.txt | AC | 20 ms | 1664 KB |
subtask1_1.txt | AC | 2 ms | 768 KB |
subtask1_10.txt | AC | 28 ms | 2304 KB |
subtask1_11.txt | AC | 23 ms | 2304 KB |
subtask1_12.txt | AC | 33 ms | 2304 KB |
subtask1_13.txt | AC | 33 ms | 2304 KB |
subtask1_14.txt | AC | 33 ms | 2304 KB |
subtask1_2.txt | AC | 6 ms | 896 KB |
subtask1_3.txt | AC | 28 ms | 2048 KB |
subtask1_4.txt | AC | 32 ms | 2304 KB |
subtask1_5.txt | AC | 5 ms | 896 KB |
subtask1_6.txt | AC | 24 ms | 1920 KB |
subtask1_7.txt | AC | 13 ms | 1280 KB |
subtask1_8.txt | AC | 28 ms | 2048 KB |
subtask1_9.txt | AC | 15 ms | 1408 KB |