Submission #1551927
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
//#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned __int128 HASH;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll,int> plli;
typedef pair<double, int> pdbi;
typedef pair<int,pii> pipii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;
#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
const ll hmod1 = 999999937;
const ll hmod2 = 1000000000 + 9;
const ll INF = 1<<30;
const ll mod = 1000000000 + 7;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const double pi = 3.141592653589793;
int n, m;
int a[55];
vector<int> s1;
vector<int> s2;
signed main(){
cin.tie(0);
ios::sync_with_stdio(false);
cin >> n >> m;
rep(i, n) cin >> a[i];
int n1 = n / 2;
int n2 = n - n1;
rep(i, 1<<n1) {
int tmp = 0;
rep(j, n1) {
if (i>>j&1) tmp += a[j];
}
s1.push_back(tmp);
}
sort(all(s1));
rep(i, 1<<n2) {
int tmp = 0;
rep(j, n2) {
if (i>>j&1) tmp += a[j + n1];
}
s2.push_back(tmp);
}
sort(all(s2));
int ans = 10000000;
rep(i, s1.size()) {
int idx = lower_bound(all(s2), m - s1[i]) - s2.begin();
if (idx == s2.size()) continue;
ans = min(ans, s1[i] + s2[idx]);
}
if (ans == 10000000) cout << -1 << endl;
else cout << ans << endl;
}
Submission Info
Submission Time |
|
Task |
G - haruki の覚醒め |
User |
roto_37 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1922 Byte |
Status |
TLE |
Exec Time |
2104 ms |
Memory |
133340 KB |
Judge Result
Set Name |
All |
Score / Max Score |
0 / 100 |
Status |
|
Set Name |
Test Cases |
All |
00-sample1, 00-sample2, corner00, corner01, random00-00, random00-01, random00-02, random00-03, random00-04, random00-05, random00-06, random00-07, random00-08, random00-09, random00-10, random00-11, random00-12, random00-13, random00-14, random00-15, random00-16, random00-17, random00-18, random00-19, random00-20, random00-21, random00-22, random00-23, random00-24, random00-25, random00-26, random00-27, random00-28, random00-29 |
Case Name |
Status |
Exec Time |
Memory |
00-sample1 |
AC |
1 ms |
256 KB |
00-sample2 |
AC |
1 ms |
256 KB |
corner00 |
AC |
1 ms |
256 KB |
corner01 |
TLE |
2104 ms |
133340 KB |
random00-00 |
AC |
1 ms |
256 KB |
random00-01 |
AC |
1 ms |
256 KB |
random00-02 |
AC |
136 ms |
5360 KB |
random00-03 |
AC |
2 ms |
256 KB |
random00-04 |
AC |
100 ms |
3444 KB |
random00-05 |
AC |
2 ms |
384 KB |
random00-06 |
AC |
1 ms |
256 KB |
random00-07 |
AC |
1697 ms |
50788 KB |
random00-08 |
AC |
1 ms |
256 KB |
random00-09 |
AC |
1721 ms |
51556 KB |
random00-10 |
AC |
1 ms |
256 KB |
random00-11 |
AC |
1 ms |
256 KB |
random00-12 |
AC |
25 ms |
1148 KB |
random00-13 |
AC |
50 ms |
1912 KB |
random00-14 |
AC |
1 ms |
256 KB |
random00-15 |
AC |
1 ms |
256 KB |
random00-16 |
AC |
138 ms |
5360 KB |
random00-17 |
AC |
25 ms |
1148 KB |
random00-18 |
AC |
1 ms |
256 KB |
random00-19 |
AC |
1 ms |
256 KB |
random00-20 |
AC |
1166 ms |
41828 KB |
random00-21 |
AC |
1 ms |
256 KB |
random00-22 |
AC |
1 ms |
256 KB |
random00-23 |
AC |
17 ms |
892 KB |
random00-24 |
AC |
1 ms |
256 KB |
random00-25 |
AC |
2 ms |
256 KB |
random00-26 |
AC |
5 ms |
512 KB |
random00-27 |
AC |
33 ms |
1528 KB |
random00-28 |
AC |
1 ms |
256 KB |
random00-29 |
AC |
1728 ms |
50660 KB |