提出 #746449

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define pb push_back
#define mp make_pair
#define fi first
#define se second

int dp[100005]={};

int main()
{
	int n,a,b,MAX=1;
	vector<pii>v,w,x;
	set<int>s,t;
	v.pb(mp(0,0));
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a>>b;
		v.pb(mp(a,b));
	}
	sort(v.begin(),v.end());
	for(int i=0;i<=n;i++)
	{
		if(s.find(v[i].fi)==s.end())
		{
			w.pb(mp(v[i].fi,v[i].se));
			s.insert(v[i].fi);
		}
	}
	for(int i=w.size()-1;i>=0;i--)
	{
		if(t.find(w[i].se)==t.end())
		{
			x.pb(mp(w[i].fi,w[i].se));
			s.insert(w[i].se);
		}
	}
	sort(x.begin(),x.end());
	dp[0]=0,dp[1]=1;
	if(x.size()==2)cout<<1<<endl;
	else
	{
		for(int i=2;i<=x.size();i++)
		{
			if(x[i].fi>x[i-1].fi&&x[i].se>w[i-1].se)dp[i]=max(dp[i-1]+1,dp[i-2]);
			else if(x[i].fi>x[i-2].fi&&x[i].se>x[i-2].se)max(dp[i-1],dp[i]=dp[i-2]+1);
			else dp[i]=dp[i-1];
		}
		cout<<dp[x.size()-1]<<endl;
	}
	return 0;
}

提出情報

提出日時
問題 D - プレゼント
ユーザ kkrtjnj3829
言語 C++14 (GCC 5.4.1)
得点 0
コード長 1038 Byte
結果 WA
実行時間 200 ms
メモリ 8052 KiB

ジャッジ結果

セット名 Sample Subtask0 All
得点 / 配点 0 / 0 0 / 30 0 / 70
結果
AC × 4
AC × 6
WA × 13
AC × 4
WA × 26
セット名 テストケース
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 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
ケース名 結果 実行時間 メモリ
sample0.txt AC 4 ms 256 KiB
sample1.txt AC 4 ms 256 KiB
sample2.txt AC 4 ms 256 KiB
sample3.txt AC 4 ms 256 KiB
subtask0_0.txt WA 5 ms 256 KiB
subtask0_1.txt WA 4 ms 256 KiB
subtask0_10.txt AC 5 ms 384 KiB
subtask0_11.txt AC 5 ms 384 KiB
subtask0_12.txt WA 6 ms 384 KiB
subtask0_13.txt WA 6 ms 384 KiB
subtask0_14.txt WA 6 ms 384 KiB
subtask0_2.txt WA 4 ms 256 KiB
subtask0_3.txt WA 4 ms 256 KiB
subtask0_4.txt WA 6 ms 384 KiB
subtask0_5.txt WA 4 ms 256 KiB
subtask0_6.txt WA 5 ms 384 KiB
subtask0_7.txt WA 6 ms 384 KiB
subtask0_8.txt WA 6 ms 384 KiB
subtask0_9.txt WA 7 ms 256 KiB
subtask1_0.txt WA 132 ms 4728 KiB
subtask1_1.txt WA 7 ms 512 KiB
subtask1_10.txt AC 200 ms 8052 KiB
subtask1_11.txt AC 189 ms 8052 KiB
subtask1_12.txt WA 196 ms 6004 KiB
subtask1_13.txt WA 195 ms 6004 KiB
subtask1_14.txt WA 194 ms 6004 KiB
subtask1_2.txt WA 35 ms 1920 KiB
subtask1_3.txt WA 167 ms 5620 KiB
subtask1_4.txt WA 191 ms 6004 KiB
subtask1_5.txt WA 31 ms 1792 KiB
subtask1_6.txt WA 149 ms 5236 KiB
subtask1_7.txt WA 84 ms 3832 KiB
subtask1_8.txt WA 175 ms 5620 KiB
subtask1_9.txt WA 91 ms 4088 KiB