Submission #1178050
Source Code Expand
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include <array>
typedef long long int ll;
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define REP(i,n) for (int i=0;i<(n);i++)
#define EREP(i,n) for (int i=1;i<=(n);i++)
#define EVEL 1
#ifndef EVEL
#define DEB(X) cout << #X << ":" <<X<<" " ;
#define TF(f) f ? cout<<"true " : cout<<"false ";
#define END cout<<"\n";
#else
#define DEB(X) {X;}
#define TF(f) {f;}
#define END {}
#endif
const int MOD = 1000000007;
const int INF = 1000000;
#define NMAX 5000
#define MAX 10
ll sum[NMAX + 1], temp, buff = 0;
int N, K, ans = 0;
int A[100010];
int count = 0;
std::array<std::array<bool, NMAX + 10>, NMAX + 10> dp, dp1;
std::array<std::array<bool, NMAX + 10>, NMAX + 10> vis, vis1;
int low = 0, high, mid;
bool dfs(ll x, ll y) {
// DEB(x)DEB(y)END
if (y<0)return false;
if (vis[x][y]) {
return dp[x][y];
}
else vis[x][y] = true;
if (y == 0) { dp[x][y] = true; /*DEB(dp[x][y])DEB(x)DEB(y)END*/ return dp[x][y]; }
if (x == N) { dp[x][y] = false;/*DEB(dp[x][y])DEB(x)DEB(y)END*/ return dp[x][y]; }
if (dfs(x + 1, y) || dfs(x + 1, y - A[x])) {
dp[x][y] = true;
}
else dp[x][y] = false;
//DEB(dp[x][y])DEB(x)DEB(y)END
return dp[x][y];
}
bool front(ll x, ll y) {
if (y<0)return false;
if (x<0) {
//DEB(dp1[x][y])DEB(x)DEB(y)END
return false;
}
if (vis1[x][y]) {
return dp1[x][y];
}
else vis1[x][y] = true;
if (y == 0) {
dp1[x][y] = true; //DEB(dp1[x][y])DEB(x)DEB(y)END
return dp1[x][y];
}
if (front(x - 1, y) || front(x - 1, y - A[x])) {
dp1[x][y] = true;
}
else dp1[x][y] = false;
//DEB(dp1[x][y])DEB(x)DEB(y)END
return dp1[x][y];
}
#if 0
int main() {
ios_base::sync_with_stdio(false);
cin >> N >> K;
ans = N;
REP(i, N) { cin >> A[i]; }
sort(A, A + N);
high = N - 1;
REP(i, N) {
bool m = false;
FOR(j, K - A[i], K) {
if (j<0)j = 0;
//if(front(i,j)) m=true;
REP(k, K) {
//if(j+k>K)break;
DEB(i)DEB(j)DEB(k)
TF(front(i, j))
TF(dfs(i, k))
TF(dfs(i, k) && front(i, j))
END
if (dfs(i, k) && front(i, j)) {
ans = i;
if (i == N - 1)ans = 0;
m = true;
break;
}
}
if (m)break;
}
if (m)break;
}
cout << ans << endl;
}
#else
int main() {
ios_base::sync_with_stdio(false);
cin >> N >> K;
ans = N;
REP(i, N) { cin >> A[i]; }
sort(A, A + N);
REP(i, N) {
bool m = false;
REP(k, K) {
FOR(j, K - A[i] - k, K-k+1) {
if (j<0)j = 0;
DEB(i)DEB(j)DEB(k)
TF(front(i, j))
TF(dfs(i, k))
TF(dfs(i, k) && front(i, j))
END
if (dfs(i+1, k) && front(i-1, j)) {
//必要
ans = i;
//if (i == N - 1)ans = 0;
m = true;
break;
}
}
if (m)break;
}
if (m)break;
}
cout << ans << endl;
}
#endif
Submission Info
Submission Time |
|
Task |
D - No Need |
User |
eiya |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2996 Byte |
Status |
WA |
Exec Time |
1389 ms |
Memory |
98816 KB |
Judge Result
Set Name |
Sample |
Subtask |
All |
Score / Max Score |
0 / 0 |
0 / 300 |
0 / 300 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
0_000.txt, 0_001.txt, 0_002.txt |
Subtask |
0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt |
All |
0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 2_026.txt, 2_027.txt, 2_028.txt, 2_029.txt, 2_030.txt, 2_031.txt, 2_032.txt, 2_033.txt, 2_034.txt, 2_035.txt, 2_036.txt, 2_037.txt, 2_038.txt, 2_039.txt, 2_040.txt, 2_041.txt, 2_042.txt, 2_043.txt, 2_044.txt, 2_045.txt, 2_046.txt, 2_047.txt, 2_048.txt, 2_049.txt, 2_050.txt |
Case Name |
Status |
Exec Time |
Memory |
0_000.txt |
AC |
3 ms |
8448 KB |
0_001.txt |
AC |
3 ms |
8448 KB |
0_002.txt |
AC |
3 ms |
8448 KB |
1_003.txt |
WA |
3 ms |
8448 KB |
1_004.txt |
WA |
3 ms |
8448 KB |
1_005.txt |
WA |
4 ms |
8448 KB |
1_006.txt |
AC |
5 ms |
10624 KB |
1_007.txt |
WA |
5 ms |
10624 KB |
1_008.txt |
WA |
13 ms |
16384 KB |
1_009.txt |
AC |
13 ms |
16384 KB |
1_010.txt |
WA |
8 ms |
12544 KB |
1_011.txt |
WA |
3 ms |
8448 KB |
1_012.txt |
WA |
7 ms |
12544 KB |
1_013.txt |
WA |
3 ms |
8448 KB |
1_014.txt |
WA |
3 ms |
8448 KB |
1_015.txt |
WA |
6 ms |
12544 KB |
1_016.txt |
AC |
4 ms |
8448 KB |
1_017.txt |
WA |
4 ms |
8448 KB |
1_018.txt |
AC |
4 ms |
8448 KB |
1_019.txt |
AC |
6 ms |
12544 KB |
1_020.txt |
WA |
4 ms |
12544 KB |
1_021.txt |
WA |
5 ms |
12544 KB |
1_022.txt |
WA |
4 ms |
12544 KB |
1_023.txt |
WA |
4 ms |
12544 KB |
1_024.txt |
AC |
8 ms |
15488 KB |
1_025.txt |
AC |
9 ms |
15488 KB |
2_026.txt |
WA |
145 ms |
8448 KB |
2_027.txt |
AC |
15 ms |
10624 KB |
2_028.txt |
WA |
15 ms |
10624 KB |
2_029.txt |
WA |
1389 ms |
98816 KB |
2_030.txt |
AC |
1389 ms |
98816 KB |
2_031.txt |
WA |
775 ms |
53760 KB |
2_032.txt |
WA |
4 ms |
8448 KB |
2_033.txt |
WA |
774 ms |
53888 KB |
2_034.txt |
WA |
3 ms |
8448 KB |
2_035.txt |
WA |
4 ms |
8448 KB |
2_036.txt |
WA |
548 ms |
53760 KB |
2_037.txt |
AC |
164 ms |
10496 KB |
2_038.txt |
WA |
165 ms |
10624 KB |
2_039.txt |
AC |
164 ms |
10624 KB |
2_040.txt |
AC |
680 ms |
53760 KB |
2_041.txt |
WA |
296 ms |
53760 KB |
2_042.txt |
WA |
453 ms |
53760 KB |
2_043.txt |
WA |
272 ms |
41344 KB |
2_044.txt |
WA |
302 ms |
53760 KB |
2_045.txt |
WA |
155 ms |
49664 KB |
2_046.txt |
AC |
508 ms |
78336 KB |
2_047.txt |
AC |
833 ms |
80384 KB |
2_048.txt |
AC |
1144 ms |
78336 KB |
2_049.txt |
AC |
1106 ms |
74240 KB |
2_050.txt |
AC |
1079 ms |
70144 KB |